1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <algorithm>  5 #include <cmath>  6 #include <string>  7 #include <map>  8 #include <stack>  9 #include <vector> 10 #include <set> 11 #include <queue> 12 #pragma comment (linker,"/STACK:102400000,102400000") 13 #define maxn 1005 14 #define MAXN 2005 15 #define mod 1000000009 16 #define INF 0x3f3f3f3f 17 #define pi acos(-1.0) 18 #define eps 1e-6 19 typedef long long ll; 20 using namespace std; 21  22 int d[maxn];    //标号 23 int mp[maxn][maxn];     //残留网络，初始为原图 24 int num[maxn];      //num[i]表示标号为i的顶点数有多少 25 int pre[maxn];      //记录前驱 26 int n,m,s,t;        //n个顶点，m条边，源点s，汇点t 27  28 void init()     //bfs计算标号，汇点t的标号为零 29 { 30     int k; 31     queue<int>Q; 32     memset(d,INF,sizeof(d));  //初始化d数组为无穷大 33     memset(num,0,sizeof(num));  //初始化num数组num 34     Q.push(t);      //汇点t入队列 35     d[t]=0;     //汇点标号为零 36     num[0]=1;   //标号为0的顶点数为1 37     while (!Q.empty()) 38     { 39         k=Q.front(); 40         Q.pop(); 41         for (int i=0;i<n;i++) 42         { 43             if (d[i]>=n&&mp[i][k]>0) 44             { 45                 d[i]=d[k]+1; 46                 Q.push(i); 47                 num[d[i]]++; 48             } 49         } 50     } 51 } 52  53 int findAlowArc(int i)      //从i出发寻找允许弧 54 { 55     int j; 56     for (j=0;j<n;j++) 57         if (mp[i][j]>0&&d[i]==d[j]+1) 58             return j; 59     return -1; 60 } 61  62 int reLable(int i)      //重新标号 63 { 64     int mm=INF; 65     for (int j=0;j<n;j++) 66         if (mp[i][j]>0) 67             mm=min(mm,d[j]+1); 68     return mm==INF?m:mm; 69 } 70  71 int maxFlow(int s,int t)       //求从源点s出发的最大流 72 { 73     int flow=0,i=s,j; 74     int delta;          //增量 75     memset(pre,-1,sizeof(pre)); 76     while (d[s]<n) 77     { 78         j=findAlowArc(i); 79         if (j>=0) 80         { 81             pre[j]=i; 82             i=j; 83             if (i==t)       //更新残留网络 84             { 85                 delta=INF; 86                 for (i=t;i!=s;i=pre[i]) 87                     delta=min(delta,mp[pre[i]][i]); 88                 for (i=t;i!=s;i=pre[i]) 89                     mp[pre[i]][i]-=delta,mp[i][pre[i]]+=delta; 90                 flow+=delta; 91             } 92         } 93         else 94         { 95             int x=reLable(i);       //重新标号 96             num[x]++; 97             num[d[i]]--; 98             if (num[d[i]]==0)        //间隙优化 99                 return flow;100             d[i]=x;101             if (i!=s)102                 i=pre[i];103         }104     }105     return flow;106 }107 108 int main()109 {110     int u,v,c;  //弧的起点，终点，容量111     while (scanf("%d%d",&n,&m)!=EOF)  //读入顶点个数n和弧数m112     {113         memset(mp,0,sizeof(mp));114         for (int i=0;i<m;i++)115         {116             scanf("%d%d%d",&u,&v,&c);117             mp[u][v]=c;118         }119         s=0,t=n-1;120         init();121         printf("%d\n",maxFlow(0,n-1));122     }123     return 0;124 }125 /*126 6 10127 0 1 8128 0 2 4129 1 3 2130 1 4 2131 2 1 4132 2 3 1133 2 4 4134 3 4 6135 3 5 9136 4 5 7137 */