裸的全局最小割了吧 有重边，用邻接矩阵的时候要小心
#include<iostream> #include<cstdio> #include<bitset> #include<cstring> #define MOD 1000000007 #define maxn 509 using namespace std; int a[590][590],wage[maxn],in[maxn],vis[maxn]; int n,x,y,v; int find(int& s,int& t) { int max_flow,u=0; memset(vis,0,sizeof(vis)); memset(wage,0,sizeof(wage)); s=t=-1; int uu=n; while(uu--) { int maxx=-0x3f3f3f3f; for(int i=1;i<=n;i++)if(!vis[i] && !in[i] && maxx < wage[i]) maxx = wage[u=i]; vis[u]=1; if(u==t)return max_flow; max_flow = maxx; s = t; t = u; for(int i=1;i<=n;i++)if(!vis[i] && !in[i])wage[i]+=a[u][i]; } return max_flow; } int main() { int m,k; while(scanf("%d%d",&n,&m)!=EOF) { memset(in,0,sizeof(in)); memset(a,0,sizeof(a)); for(int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&v); x++;y++; a[x][y]+=v; a[y][x]+=v; } int s,t,ans = 0x3f3f3f3f; for(int i=1;i<n;i++) { int u = find(s,t); in[t]=1; ans = min(ans,u); for(int j=1;j<=n;j++)if(!in[j] && j !=s) { a[s][j]+=a[t][j]; a[j][s]+=a[j][t]; } } printf("%d\n",ans); } return 0; }