1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5  6 const int MAXN=150; 7 const int inf=10000000; 8 int vis[MAXN],combine[MAXN],wan[MAXN]; 9 int map[MAXN][MAXN];10 int n,m,t;11 int mincut,S,T;12 13 void seacut(){14     int Max; int p;15     S=T=-1;16     memset(vis,0,sizeof(vis));17     memset(wan,0,sizeof(wan));18     for(int i=0;i<n;i++){19         Max=-inf;20         for(int j=0;j<n;j++){21             if(!combine[j]&&!vis[j]&&wan[j]>Max){22                 Max=wan[j]; p=j;23             }24         }25     //    cout<<p<<endl;26         if(p==T) return;27         S=T;T=p;28         vis[T]=1;29         for(int j=0;j<n;j++){30             if(!combine[j]&&!vis[j]){31                 wan[j]+=map[T][j];32             }33         }34     }35 }36 37 void storewanger(){38     mincut=inf;39     memset(combine,0,sizeof(combine));40     for(int i=0;i<n-1;i++){41         seacut();42         if(wan[T]<mincut) mincut=wan[T];43         if(mincut==0) return;44         combine[T]=1;45         for(int j=0;j<n;j++){46             if(!combine[j]){47                 map[S][j]+=map[T][j];48                 map[j][S]+=map[j][T];49             }50         }51     }52 }53 54 int main(){55     int u,v,w;56     while(scanf("%d%d",&n,&m)!=EOF){57         memset(map,0,sizeof(map));58         for(int i=0;i<m;i++){59             scanf("%d%d%d",&u,&v,&w);60             map[u][v]+=w;61             map[v][u]+=w;62         //    cout<<"YES"<<endl;63         }64     //    cout<<"YES"<<endl;65         storewanger();66         printf("%d\n",mincut);67     }68     return 0;69 }