https://vjudge.net/problem/HDU-3691 给定一个图，每个图中的边权都是流量。 已经确定一个图的初始点，问你如何设置能够使他的最大流最小 （即最小割最小）。 固定一个点，用sw算法求 最小割即可。
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> using namespace std; const int maxn = 550; const int inf = 1000000000; int n,r; int edge[maxn][maxn],dist[maxn]; bool vis[maxn], bin[maxn]; void init() { memset(edge, 0, sizeof(edge)); memset(bin, false, sizeof(bin)); } int contract( int &s, int &t ) // 寻找 s,t { memset(dist, 0, sizeof(dist)); memset(vis, false, sizeof(vis)); int i, j, k, mincut, maxc; for(i = 1; i <=n; i++) { k = -1; maxc = -1; for(j = 1; j <=n; j++)if(!bin[j] && !vis[j] && dist[j] > maxc) { k = j; maxc = dist[j]; } if(k == -1)return mincut; s = t; t = k; mincut = maxc; vis[k] = true; for(j = 1; j <=n; j++)if(!bin[j] && !vis[j]) dist[j] += edge[k][j]; } return mincut; } int Stoer_Wagner(int s) { int mincut, i, j, t, ans; for(mincut = 1e8+5, i = 1; i <n; i++) { ans = contract( s, t ); bin[t] = true; if(mincut > ans)mincut = ans; if(mincut == 0)return 0; for(j = 1; j <=n; j++)if(!bin[j]) edge[s][j] = (edge[j][s] += edge[j][t]); } return mincut; } int main() { int m; int s; int a,b,c; while(cin>>n>>m>>s) { init(); //memset(edge,0,sizeof(edge)); if(n==0&&m==0&&s==0) break; for(int i=1;i<=m;i++) {scanf("%d%d%d",&a,&b,&c); edge[a][b]+=c; edge[b][a]+=c; } cout<<Stoer_Wagner(s)<<endl; } return 0; }