无向图全局最小割

无向图的割

无向图的割:在联通无向图 $G$ 中,通过割去一些边使得 $G$ 变成两个连通分量,则称那些边为 $G$ 的一个

全局最小割:所有中权值和最小的割。

Stoer-Wagner 算法

算法基于这样一个事实:对于图中的任意两点 $s,t$,它们要么在全局最小割的同侧,要么在全局最小割的两侧。

  • 每次从图中任意找一个最小割 $(s,t)$,然后更新答案。
  • 然后将 $(s,t)$ 两点合并。
  • 继续找最小割,直到只剩余一个点为止。

证明还在学习(意思就是大概率咕咕

时间复杂度:$O(n ^ 3)$

模板题 poj 2914

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// O(n^3)  1-index
// 不能有负权边(可以改成加偏移的,不过有点烦
struct StoerWagner {
int n;
int mask[maxn]; // 因为有删点的操作,所以用mask[i]来表示第i个位置是几号点
int G[maxn][maxn]; // 邻接矩阵
int d[maxn]; // 表示集合到各个点的距离
bool vis[maxn]; // 该点是否加入了集合
void init(int n) {
this->n = n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) G[i][j] = 0;
}
void addedge(int u, int v, int c) {
G[u][v] += c;
G[v][u] += c;
}
int solve() {
int res = INF;
for (int i = 1; i <= n; i++) mask[i] = i;
while (n > 1) {
int k, pre = 1; // 默认1号点是集合的第一个点
for (int i = 1; i <= n; i++) vis[mask[i]] = 0, d[mask[i]] = 0;
vis[mask[pre]] = true;
for (int i = 2; i <= n; i++) {
k = -1;
for (int j = 1; j <= n; j++) { // 寻找距离最远的点加入集合
if (!vis[mask[j]]) {
d[mask[j]] += G[mask[pre]][mask[j]];
if (k == -1 || d[mask[k]] < d[mask[j]]) k = j;
}
}
vis[mask[k]] = true; // 加入集合
if (i == n) { // 只剩一个点
res = min(res, d[mask[k]]);
for (int j = 1; j <= n; j++) { // 修改边权
G[mask[pre]][mask[j]] += G[mask[j]][mask[k]];
G[mask[j]][mask[pre]] += G[mask[j]][mask[k]];
}
mask[k] = mask[n--]; // 去掉最后加入的点
}
pre = k;
}
}
return res;
}
} sw;