1 #include<stdio.h>
2 #include<string.h>
3 #include<queue>
4 using namespace std;
5
6 int cap[205][205],pre[205];//cap 残量（残余网络），n 汇点
7 int n;
8 queue<int>p;
9
10 int _min(int a,int b)
11 {
12 return a<b?a:b;
13 }
14
15 void bfs()
16 {
17 int Maxflow = 0, i;
18 while(1)
19 {
20 pre[1]=1;
21 p.push(1);
22 int min=999999999;
23 memset(pre,0,sizeof(pre));
24 while(!p.empty())
25 {
26 int u=p.front();
27 p.pop();
28 for(i=1;i<=n;i++)
29 {
30 if(pre[i]==0 && cap[u][i]>0)
31 {
32 pre[i]=u;
33 p.push(i);
34 min=_min(min,cap[u][i]);//找到此时遍历到的所有边的最短值，并不是增广路上的最小容量值
35 }
36 }
37 }
38 if(pre[n]==0) break;
39
40 for(int s=n; s!=1; s=pre[s]){
41 cap[pre[s]][s]-= min;
42 cap[s][pre[s]]+= min;
43 }
44 Maxflow += min;
45 }
46 printf("%d\n", Maxflow);
47 }
48
49 int main()
50 {
51 int m, a, b, c, i;
52 while(scanf("%d%d",&m,&n)!=EOF)
53 {
54 memset(cap,0,sizeof(cap));
55 for(i=0;i<m;i++)
56 {
57 scanf("%d%d%d",&a,&b,&c);
58 cap[a][b]+=c;
59 }
60 bfs();
61 }
62 return 0;
63 }
