Ford-Fulkerson算法
基本没什么技巧
View Code
1 #include<cstdio> 2 #include<cstring> 3 #include<cstdlib> 4 #include<queue> 5 using namespace std; 6 #define N 1005 7 #define inf 9999999 8 int map[N][N],pre[N],vis[N]; 9 int start,eend,ans; 10 11 void max_flow(int n) 12 { 13 int i,j,k; 14 while(1) 15 { 16 queue<int>q; 17 while(!q.empty())q.pop(); 18 19 memset(vis,0,sizeof(vis)); 20 //memset(pre,-1,sizeof(pre)); 21 22 q.push(start); 23 vis[start]=1; 24 while(!q.empty()) 25 { 26 k=q.front(); 27 q.pop(); 28 if(k==eend) break;//找到了增广路 29 for(i=1;i<=n;i++) 30 { 31 if(vis[i]==1||map[k][i]==0)continue; 32 q.push(i); 33 vis[i]=1; 34 pre[i]=k; 35 } 36 } 37 38 if(vis[eend]==0)break;//无法找到增广路 39 40 int min=inf; 41 for(i=eend;i!=start;i=pre[i]) 42 { 43 if(map[pre[i]][i]<min) 44 { 45 min=map[pre[i]][i]; 46 } 47 } 48 49 for(i=eend;i!=start;i=pre[i]) 50 { 51 map[pre[i]][i]-=min; 52 map[i][pre[i]]+=min; 53 } 54 ans+=min; 55 } 56 return ; 57 } 58 59 int main() 60 { 61 int i,j,k,tcase,t; 62 int m,n,a,b,c; 63 scanf("%d",&tcase); 64 for(t=1;t<=tcase;t++) 65 { 66 scanf("%d%d",&n,&m); 67 start=1; 68 eend=n; 69 memset(map,0,sizeof(map)); 70 while(m--) 71 { 72 scanf("%d%d%d",&a,&b,&c); 73 map[a][b]+=c; 74 } 75 ans=0; 76 max_flow(n); 77 printf("Case %d: %d\n",t,ans); 78 } 79 return 0; 80 }