The weakest link
A network, airports and flights, stations and cables, servers and channels, is described by links with weights: the weight is how many flights, cables or gigabits link two nodes. Its weak spot is a set of links of the smallest total weight whose breaking makes the network fall apart into at least two parts. Find the weight of the weak spot. Which parts break off does not matter.
The third test is the real network of flights between 21 airports: the weight of a link between two airports is how many callsigns fly between them in both directions. The other networks are made up.
Input
The first line holds the number of nodes n and the number of links m (2 ≤ n ≤ 100, 0 ≤ m ≤ 5000). Then m lines a b w: a link between nodes a and b of weight w (1 ≤ w ≤ 10⁶). There may be several links between two nodes; a link of a node to itself (a = b) holds nothing together.
Output
The smallest total weight of links whose removal leaves the network disconnected. If it is disconnected from the start, the answer is 0.
Examples
Example 1
6 8 1 2 5 2 3 5 1 3 5 4 5 5 5 6 5 4 6 5 3 4 2 1 6 1
3
Example 2
4 2 1 2 7 3 4 1
0
Limits
- Time · Python
- 3000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
The first thing that comes to mind is to find the node with the smallest sum of weights of its links: cut them, and it breaks off. Check the first example: each node is held by links of weight at least 10, and the answer is 3.
2Hint 2
If two nodes that the weak spot separates were known, this would be a minimum cut between a source and a sink, a maximum flow. Any node can be taken as the source: it lies on one of the sides. And the sink?
3The idea
A global minimum cut is needed. Three ways: try every other node as the sink and compute a flow for each (n − 1 flows); Karger’s random contractions with enough repetitions; the deterministic Stoer–Wagner algorithm, which here is the simplest and fastest. All three are described in the article on the minimum cut.
4Walkthrough
Stoer–Wagner works in phases. In a phase the nodes are lined up one by one: the first any, and each next the one whose sum of link weights to those already lined up is greatest. Let s and t be the last two. Then the cut “t against all the rest” is minimal among all cuts separating s and t; its weight is the sum of t’s link weights at the moment t joined the line. Remember it and merge s and t into one node: the weak spot either separates them, and then we have already found it, or not, and then it survives the merge. After n − 1 phases one node remains, and the answer is the smallest of the phase cuts.
An n × n weight matrix is more convenient than lists: merging is adding two rows. Parallel links add up, and loops are thrown away on reading.
4+Solution
5Complexity
n − 1 phases, each choosing the next node by scanning and updating the sums: O(n²) per phase, O(n³) in all, a million steps for a hundred nodes. With a heap and adjacency lists it is O(nm + n² log n). Trying every sink with a flow for each is n times dearer than one flow, but for these sizes it also fits in time.
6Common mistakes
- The weakest node. The answer “the smallest sum of link weights of a single node” is
wrong.py. It is often right: in the flight network the weak spot is an airport with two callsigns. But a group of nodes tightly linked among themselves may hold on to the rest of the network more weakly than any of its nodes, like the two triangles in the first example. - A disconnected network. Every node in the second example has a link, yet the answer is 0: the network has already fallen apart.
- Loops. A link of a node to itself must not be added to its weight: it connects nothing.