Graph Contest 3 P3 - Cable TV

View as PDF
Submit solution
Points: 7
Time limit: 0.6s
Memory limit: 32M
Problem type

You would like to provide citizens of a newly constructed neighborhood with cable television. As a computer scientist, you know this calls for... wires!

Surveyors have done their work and have given you the cost of connecting pairs of locations. However, they have also warned you that certain links might be dangerous - there is a risk of interference from power lines and such. Find the minimum cost to connect all the houses, minimizing the cost but above all minimizing the number of dangerous links used.

Input Specification

N \le 100, the number of locations.
M \le 10\,000, the number of possible links.
M lines, each with four integers a, b, c, d. Each line signifies a possible (bidirectional) link between locations a and b, with cost c. d will be 1 if the link is dangerous, and 0 otherwise.

Output Specification

Two integers.
Output a) the minimum number of dangerous links required and b) the total minimum cost.

Sample Input

4 4
1 2 2 0
2 3 1 1
3 1 1 0
3 4 1 1

Sample Output

1 4

Take 1-2, 3-1, and 3-4.
The use of one dangerous cable is inevitable, but we can avoid the use of the other.

Comments


  • 1
    MintSoapBar  commented on Nov. 26, 2023, 10:14 p.m.

    What are the limits on cost?


    • 1
      htoshiro  commented on Nov. 27, 2023, 12:43 a.m.

      there is no limit (i think, correct me if im wrong) it's just the min cost when you also minimize the number of dangerous edges/links