这题给出一个无向图和一个源点,让你求从这个点出发到某个点最大流的最小值。由最小割最大流定理,最全局最小割就可以了,但是因为我没有模版所以这题就悲剧了……之前找到了一个模版改半天没改好,后来发现只要改一个地方就行了,AC了发现速度还挺快的,代码也不长,嗯,这个模版要收藏
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int MAXN = 305; const int MAXV = 0x3F3F3F3F; int n,m,v[MAXN],mat[MAXN][MAXN],dis[MAXN]; bool vis[MAXN]; int res,s; int Stoer_Wagner(int n) { int i, j; int res = MAXV; for (i = 0; i < n; i++) v[i] = i+1;//初始化第i个结点就是i while (n > 1) { int maxp = 1,prev = 0; for (i = 1; i < n; i++) //初始化到已圈集合的割大小,并找出最大距离的顶点 { dis[v[i]] = mat[v[0]][v[i]]; if (dis[v[i]] > dis[v[maxp]]) maxp = i; } memset(vis, 0, sizeof(vis)); vis[v[0]] = true; for (i = 1; i < n; i++) { if (i == n - 1) //只剩最后一个没加入集合的点,更新最小割 { res = min(res,dis[v[maxp]]); for (j = 0; j < n; j++) //合并最后一个点以及推出它的集合中的点 { mat[v[prev]][v[j]] += mat[v[j]][v[maxp]]; mat[v[j]][v[prev]] = mat[v[prev]][v[j]]; } v[maxp] = v[--n];//第maxp个节点去掉,第n个节点变成第maxp个 } vis[v[maxp]] = true; prev = maxp; maxp = -1; for (j = 1; j < n; j++) if (!vis[v[j]]) //将上次求的maxp加入集合,合并与它相邻的边到割集 { dis[v[j]] += mat[v[prev]][v[j]]; if (maxp == -1 || dis[v[maxp]] < dis[v[j]]) maxp = j; } } } return res; } int main() { //freopen("input.txt","r",stdin); while (scanf("%d%d%d", &n, &m, &s),n||m||s) { memset(mat,0,sizeof (mat)); int x,y,z; while (m--) { scanf("%d%d%d",&x,&y,&z); mat[x][y] += z; mat[y][x] += z; } printf("%d\n",Stoer_Wagner(n)); } }