1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4  5 #define _clr(x, y) memset(x, y, sizeof (x)) 6 #define Min(x, y) (x < y ? x : y) 7 #define INF 0x3f3f3f3f 8 #define N 210 9 10 int map[N][N];11 int pre[N], Sta[N];12 bool used[N];13 int n, m;14 15 //bfs判断s--t之间是否还存在增广路16 bool bfs(int s, int t)17 {18     _clr(used, 0);19     _clr(pre, -1);20     int top=1;21     Sta[top++] = s;22     used[s] = true;23     while(top)24     {25         int v = Sta[--top];26         for(int i=1; i<=n; i++)27         {28             if(map[v][i] && !used[i])29             {30                 used[i] = true;31                 pre[i] = v;32                 if(i==t)33                     return true;34                 Sta[top++] = i;35             }36         }37     }38     return false;39 }40 41 int EK(int s, int t)42 {43     //初始化最大流为044     int maxFlow=0, d;45 46     //若s--t之间存在增广路47     while(bfs(s, t))48     {49         d = INF;50         //找到最小的可增量51         for(int i=t; i!=s; i=pre[i])52             d = Min(d, map[pre[i]][i]);53 54         //添加反向边，更新残留网络55         for(int i=t; i!=s; i=pre[i])56         {57             map[pre[i]][i] -= d;58             map[i][pre[i]] += d;59         }60         maxFlow += d;61     }62     return maxFlow;63 }64 65 66 int main()67 {68     int x, y, z;69     while(~scanf("%d%d", &m, &n))70     {71         _clr(map, 0);72         for(int i=0; i<m; i++)73         {74             scanf("%d%d%d",&x, &y, &z);75             map[x][y] += z;76         }77         printf("%d\n",EK(1, n));78     }79     return 0;80 }