Designing a High-Speed Rail Network
Time limit2sMemory limit128 MB
Given a cost matrix where negative values mark already-built rail lines, compute the minimum spanning tree cost forcing existing lines and list the new lines to build.
- Level
Medium5 of 10
- Topics
- Minimum spanning tree, Union-find, Greedy, Sorting
- Solved
- No attempts yet
Problem
A country has N cities, and the goal is to make every city reachable from every other city using only high-speed rail.
Some pairs of cities already have rail lines. Existing lines are not removed, and their costs are included in the total project cost. For pairs that do not yet have a line, a new high-speed rail line may be built at the given cost.
Add new lines so that the whole network becomes connected, and output the minimum possible total cost together with the newly built lines.
Input
The first line contains the number of cities N. (1 <= N <= 200)
Each of the next N lines contains N integers forming an adjacency matrix of costs between pairs of cities. The absolute value of each cost is at most 10,000. If the value between two cities is negative, a high-speed rail line is already installed between them, and its cost is the absolute value of that number. If the value is positive, the line is not installed yet and can be built for that cost.
Output
On the first line, output two integers C and M. C is the minimum total cost including both existing and newly built high-speed rail lines, and M is the number of newly built lines.
On each of the next M lines, output the two city numbers connected by one newly built high-speed rail line.