299
最小割-poj-2914
poj-2914-Minimum Cut
Description
Given an undirected graph, in which two vertices can be connected by multiple edges, what is the size of the minimum cut of the graph? i.e. how many edges must be removed at least to disconnect the graph into two subgraphs?
Input
Input contains multiple test cases. Each test case starts with two integers N and M (2 ≤ N ≤ 500, 0 ≤ M ≤ N × (N − 1) ⁄ 2) in one line, where N is the number of vertices. Following are M lines, each line contains M integers A, B and C (0 ≤ A, B < N, A ≠ B, C > 0), meaning that there C edges connecting vertices A and B.
Output
There is only one line for each test case, which contains the size of the minimum cut of the graph. If the graph is disconnected, print 0.
Sample Input
3 3
0 1 1
1 2 1
2 0 1
4 3
0 1 1
1 2 1
2 3 1
8 14
0 1 1
0 2 1
0 3 1
1 2 1
1 3 1
2 3 1
4 5 1
4 6 1
4 7 1
5 6 1
5 7 1
6 7 1
4 0 1
7 3 1
Sample Output
2
1
2
題目大意：有重邊的無向圖，至少刪去多少條邊能使其變為非連通圖？
分析：傳統最小割最大流算法需要枚舉匯點，複雜度為O(n^4)以上，故有時會超時。本題用Stoer-Wagner 算法。
Stoer-Wagner 算法用來求無向圖 G=(V, E)的最小割。
算法基於這樣一個原理：定義圖G的最小割為MinCut，對於任意頂點s,t ∈V，MinCut=min(s-t最小割，將s與v縮點之後的MinCut)。在此不予證明。
Stoer-Wagner 算法流程：
1. 初始置最小割MinCut 為INT_MAX。
2. 在 G中求出任意 s-t 最小割 c，更新MinCut = min(MinCut, c) 。
3. 對 G中的頂點s,t做縮點操作。若G中頂點已被縮為一個，當前MinCut即為所求。
----縮點操作：
對a和b進行縮點： 刪掉點 a, b 及邊(a, b)，加入新節點 c，對於任意 v∈V ，mat(c,v) = mat(v,c) = mat(a, v) + mat(b,v) 。
---求 G=(V, E)中任意 s-t 最小割的算法：
A 為點集，x不屬於A，定義dist[x] = ∑mat(v[i], x)，v[i]∈A 。
1. 初始令集合 A={a}，a為 V中任意點 。
2. 選取 V - A中的 dis[ x ]最大的點 x加入集合 A 。
3.更新V-A中頂點的dist[ ]。
4.若|A|=|V|，結束。令倒數第二個加入 A的點為 s，最後一個加入 A的點為 t，則s-t 最小割為dist[t]。
最後更新：2017-04-03 12:56:35