1010. The Plan That Keeps the Strongest Links

A network has n stations and m two-way links. Link i joins u and v and has strength w. Two stations may be linked more than once, at different strengths.

Choose a set of links that leaves every station reachable from every other and whose total strength is as LARGE as possible. Print that total, or -1 if the network cannot be connected at all.

4 stations, links 1-2 (1), 2-3 (2), 3-4 (3), 4-1 (4), 1-3 (5) -> 11 3 stations, links 1-2 (5), 2-3 (5) -> 10 4 stations, links 1-2 (7), 3-4 (9) -> -1 1 station, no links -> 0

Follow the first one. Taking links strongest first: 5 joins stations 1 and 3; 4 joins 4 to them; 3 would join 3 and 4, already together, so it is skipped; 2 joins station 2. Total 5 + 4 + 2 = 11.

## What most people try first

Sort by strength and take greedily WITHOUT checking whether the two ends are already connected. That keeps the strongest n - 1 links whatever they are, which is not a plan: on the first example it would take 5, 4 and 3, and the set 1-3, 4-1, 3-4 leaves station 2 completely cut off.

## Sort the other way and change nothing else

This is problem 389 with a single character altered. Sort the links in DECREASING strength and sweep:

total = 0, taken = 0 for each link (w, u, v) in decreasing w: if find(u) != find(v): merge, total = total + w, taken = taken + 1 if taken == n - 1: print total else print -1

## Why the greedy is still right after flipping the order

The exchange argument is symmetric. Suppose the sweep takes link e, the strongest link not yet redundant, and suppose some best plan P does not contain it. Adding e to P makes exactly one loop, and that loop must contain a link f whose two ends the sweep had not yet joined, because e itself joins two separate groups. Since the sweep works downwards and had not reached f, f is no stronger than e. Swap e for f: the plan stays connected and its total does not fall. Repeating this turns P into the sweep's plan without ever losing strength, so the sweep's plan is best.

The mirror of that paragraph, with "weakest" and "no weaker", is the argument for problem 389. Nothing else in either proof changes.

## The parallel links

Two links between the same pair are two separate entries. The stronger is taken and the weaker is skipped by the same redundancy test, with no deduplication written anywhere. One test has three links between the same pair at strengths 1, 1000000000 and 5, and answers 1000000000.

## The -1

A plan over n stations always has exactly n - 1 links. Counting them and comparing against n - 1 is the test, and it works for n = 1 too, where 0 links are needed and the total is 0.

## Overflow

n - 1 links of strength 10^9 total 10^14, and even a four-station test with three links of a billion reaches 3 * 10^9, which wraps to a negative number in a signed 32 bit integer whose maximum is 2147483647. That test is in the set. Use a 64 bit accumulator. Each individual strength fits in 32 bits, so this is an accumulator problem, not a reading problem.

## Cross-reference

Problem 389 minimises the same total over the same input shape. Read the two proofs side by side: they are the same three sentences with the inequality turned round, which is worth more than either problem on its own.

## Cost

Time O(m log m + (n + m) alpha(n)). Space O(n + m).

Constraints - `1 ≤ n ≤ 100000` - `0 ≤ m ≤ 200000` - `1 ≤ u, v ≤ n` and `u` is never equal to `v`. - `1 ≤ w ≤ 1000000000` - The same pair may be linked more than once.