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]。

最小割-poj-2914,布布扣,bubuko.com

最小割-poj-2914

原文：http://blog.csdn.net/chuchus/article/details/25340723