1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdio> 5 #include<queue> 6 #define INF 100000000 7 using namespace std; 8 const int N=405; 9 const int M=1000000;10 struct Node{11    int v;12    int f;13    int next;14 }edge[M];15 int n,m,u,v,w,cnt,sx,ex;16 int head[N],pre[N];17 void init(){18     cnt=0;19     memset(head,-1,sizeof(head));20 }21 void add(int u,int v,int w){22     edge[cnt].v=v;23     edge[cnt].f=w;24     edge[cnt].next=head[u];25     head[u]=cnt++;26     edge[cnt].f=0;27     edge[cnt].v=u;28     edge[cnt].next=head[v];29     head[v]=cnt++;30 }31 bool BFS(){32   memset(pre,0,sizeof(pre));33   pre[sx]=1;34   queue<int>Q;35   Q.push(sx);36  while(!Q.empty()){37      int d=Q.front();38      Q.pop();39      for(int i=head[d];i!=-1;i=edge[i].next    ){40         if(edge[i].f&&!pre[edge[i].v]){41             pre[edge[i].v]=pre[d]+1;42             Q.push(edge[i].v);43         }44      }45   }46  return pre[ex]>0;47 }48 int dinic(int flow,int ps){49     int f=flow;50      if(ps==ex)return f;51      for(int i=head[ps];i!=-1;i=edge[i].next){52         if(edge[i].f&&pre[edge[i].v]==pre[ps]+1){53             int a=edge[i].f;54             int t=dinic(min(a,flow),edge[i].v);55               edge[i].f-=t;56               edge[i^1].f+=t;57             flow-=t;58              if(flow<=0)break;59         }60 61      }62       if(f-flow<=0)pre[ps]=-1;63       return f-flow;64 }65 int solve(){66     int sum=0;67     while(BFS())68         sum+=dinic(INF,sx);69     return sum;70 }71 int main() {72     while(~scanf("%d%d",&n,&m)) {73          init();74         for(int i=1;i<=n; i++) {75            scanf("%d%d%d",&u,&v,&w);76            add(u,v,w);77         }78        sx=1;ex=m;79       printf("%d\n",solve());80     }81     return 0;82 }