毕竟是写的第一个网络流，感觉还是要好好总结一下，看了算法导论那本书之后，感觉上还是似懂非懂，直到写到这道题，看了一下别人的代码，其实就是找出能够到达那个汇点的每一个路径，然后在一路上的流量减去，相当于已经将这么多的流量运送到了汇点，然后不断找路径直到找不到能够到达的路径。。。
View Code 1 #include<iostream> 2 #include<stdio.h> 3 #include<queue> 4 #define S 205 5 using namespace std; 6 int n,m,map[S][S],link[S],answer; 7 int s,e,w; 8 void bfs() 9 { 10 int fl[S]; 11 fl[1]=0x7fffffff; 12 queue<int> q; 13 q.push(1); 14 for(int i=1;i<=m;i++)link[i]=-1; 15 while(!q.empty()) 16 { 17 int cur=q.front(); 18 q.pop(); 19 if(cur==m) 20 { 21 answer+=fl[m]; 22 int from=0,end=m; 23 while(end!=1) 24 { 25 from=link[end]; 26 map[from][end]-=fl[m]; 27 map[end][from]+=fl[m]; 28 end=from; 29 } 30 for(int i=1;i<=m;i++)link[i]=-1; 31 while(!q.empty())q.pop(); 32 fl[1]=0x7ffffff; 33 q.push(1); 34 continue; 35 } 36 for(int i=2;i<=m;i++) 37 { 38 if(map[cur][i]&&link[i]==-1) 39 { 40 link[i]=cur; 41 fl[i]=fl[cur]<map[cur][i]?fl[cur]:map[cur][i]; 42 q.push(i); 43 } 44 } 45 } 46 } 47 int main() 48 { 49 while(scanf("%d%d",&n,&m)!=EOF) 50 { 51 for(int i=1;i<=m;i++) 52 { 53 for(int j=1;j<=m;j++) 54 { 55 map[i][j]=0; 56 } 57 } 58 for(int i=0;i<n;i++) 59 { 60 scanf("%d%d%d",&s,&e,&w); 61 map[s][e]+=w; 62 } 63 answer=0; 64 bfs(); 65 printf("%d\n",answer); 66 } 67 return 0; 68 } 69
转载于:https://www.cnblogs.com/nuoyan2010/archive/2012/09/01/2667122.html
