POJ 2914 stoer-wagner 全局最小割
传送门 POJ 2914
题解 算法思路stoer−wagnerstoer-wagnerstoer−wagner 基本思路 是对于任意 222 个节点 s,ts,ts,t 全局最小割可能为 s−ts-ts−t 最小割；反之，将 s,ts,ts,t 合并为 111 个点对答案无影响。那么只要每次找到一个 s−ts-ts−t 最小割并更新答案，再将 s,ts,ts,t 合并，缩小问题规模，直到图中仅剩 111 个点为止即可。
算法的 子问题 则是如何找到一个 s−ts-ts−t 最小割。
假设已知一个不可能出现在 s−ts-ts−t 最小割中的边的端点组成的中间点集 AAA，任取一个非 {s,t}\{s,t\}{s,t} 节点即可满足这个条件。对于 s−ts-ts−t 最小割，割边 e∈Eu∈V/A,v∈V/A(u,v)∪Eu∈A,v∈V/A(u,v)e\in E_{u\in V/A,v\in V/A}(u,v)\cup E_{u\in A,v\in V/A}(u,v)e∈Eu∈V/A,v∈V/A(u,v)∪Eu∈A,v∈V/A(u,v)，在 V/AV/AV/A 中的最小割边权值是一定的。现在关注 Eu∈A,v∈V/A(u,v)E_{u\in A,v\in V/A}(u,v)Eu∈A,v∈V/A(u,v) ，对于最小割而言，此时该边集的最大值不可能出现在 s−ts-ts−t 最小割中（边数大于 222 时），将最大值对应的边属于 V/AV/AV/A 的点加入 AAA ，更新 V/AV/AV/A 中的点到 AAA 的边权和。重复更新 AAA 至 V/AV/AV/A 剩余 111 个点，该点到 AAA 的边权和即 s−ts-ts−t 最小割。
算法步骤step1：假设已知一个不可能出现在 s−ts-ts−t 最小割中的边的端点组成的中间点集 AAA，任取一个非 {s,t}\{s,t\}{s,t} 节点即可满足这个条件。
step2：寻找一个节点 v∈V/Av\in V/Av∈V/A，使任意边 Eu∈A(u,v)E_{u\in A}(u,v)Eu∈A(u,v) 都不可能出现在 s−ts-ts−t 最小割中，加入点集 AAA，更新顶点 v∈V/Av\in V/Av∈V/A 到中间点集 AAA 的边权和（形似 prim 算法），并记录最后一次加入的节点。重复 step2 直到剩余 {A,t}\{A,t\}{A,t}。
step3：此时的 A−tA-tA−t 割即 s−ts-ts−t 最小割。最后一次加入的节点为 sss，合并 s,ts,ts,t 为点 sss，即将与 ttt 相连的边连到 sss。减少总点数，跳到 step1 直到点数为 111。
代码#include
#include
#include
#include
#include
#include
#define min(a,b) (((a) (b)) ? (a) : (b))
#define abs(x) ((x) < 0 ? -(x) : (x))
#define INF 0x3f3f3f3f
#define delta 0.85
#define eps 1e-5
#define PI 3.14159265358979323846
using namespace std;
#define MAX_V 500
bool used[MAX_V];
int ver[MAX_V], flow[MAX_V]; // 顶点值，与当前中间点集的边权和
int G[MAX_V][MAX_V];
int stoer_wagner(int V){
for(int i = 0; i 1){
memset(flow, 0, sizeof(flow));
memset(used, 0, sizeof(used));
// 初始化中间点集
int s, t = 0;
for(int i = 1; i < V; i++){
used[ver[t]] = 1;
int k = -1;
for(int j = 0; j flow[ver[k]]) k = j;
}
}
// 下一个加入中间点集的点索引值
t = k;
if(i == V - 1){
mincut = min(mincut, flow[ver[t]]);
// 合并 s，t 为 s
for(int j = 0; j < V; j++){
G[ver[s]][ver[j]] += G[ver[t]][ver[j]];
G[ver[j]][ver[s]] += G[ver[j]][ver[t]];
}
ver[t] = ver[--V];
}
else{
s = t;
}
}
}
return mincut;
}
#define MAX_N 500
#define MAX_M 125000
int N, M;
int A[MAX_M], B[MAX_M], C[MAX_M];
void solve(){
memset(G, 0, sizeof(G));
for(int i = 0; i < M; i++){
// 处理重边
G[A[i]][B[i]] += C[i];
G[B[i]][A[i]] += C[i];
}
printf("%d\n", stoer_wagner(N));
}
int main(){
while(~scanf("%d%d", &N, &M)){
for(int i = 0; i < M; i++) scanf("%d%d%d", A + i, B + i, C + i);
solve();
}
return 0;
}
作者：neweryyy
