1 #include <iostream>
2 #define MAX 201
3 using namespace std;
4 int c[MAX][MAX];
5 int pre[MAX];
6 int flow; //最大流
7 int n,m; //節點數
8 int que[MAX*MAX];
9 int cp[MAX];
10 void Edmonds_Karp(int s,int t)
11 {
12 while(true)
13 {
14 cp[s]=INT_MAX;
15 memset(pre,0,sizeof(pre));
16 int head=0,tail=1;que[0]=s;
17 while(head!=tail)
18 {
19 int i=que[head++];
20 for(int j=1;j<=n;j++) //節點從0算起
21 if(j != i && !pre[j] && c[i][j]>0)
22 {
23 cp[j]=min(cp[i],c[i][j]);
24 que[tail++]=j;
25 pre[j]=i;
26 }
27 }
28 if(pre[t]==0)break;
29 int i=t;
30 while(i!=s)
31 {
32 int j=pre[i];
33 c[j][i]-=cp[t];
34 c[i][j]+=cp[t];
35 i=j;
36 }
37 flow+=cp[t];
38 }
39 printf("%d\n",flow);
40 }
41 int main()
42 {
43 int x,y,k;
44 flow=0;
45 scanf("%d%d",&m,&n);
46 for(int i=0;i<m;i++)
47 {
48 scanf("%d%d%d",&x,&y,&k);
49 c[x][y]+=k;
50 }
51 Edmonds_Karp(1,n);
52 return 0;
53 }