HDU 1532

#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
#define MaxInt 0x3f3f3f3f

using namespace std;

int m,n,f[210][210],cap[210][210],a[210],p[210];
queue<int> que;
int Edmond_Karp(int s,int t)
{
　　int flow=0;
　　while(1){//BFS找增广路
　　　　memset(a,0,sizeof(a));
　　　　a[s]=MaxInt;
　　　　que.push(s);
　　　　while(!que.empty()){
　　　　　　int u=que.front();
　　　　　　que.pop();
　　　　　　for(int v=1;v<=m;v++){//m为节点个数
　　　　　　　　if(!a[v]&&cap[u][v]>f[u][v]){
　　　　　　　　　　p[v]=u;//记录v的前驱
　　　　　　　　　　que.push(v);
　　　　　　　　　　a[v]=min(a[u],cap[u][v]-f[u][v]);//a[v]为s-v路径上的最小流量
　　　　　　　　}
　　　　　　}
　　　　}
　　　　if(a[t]==0) break;//找不到，则当前已是最大流量
　　　　for(int v=t;v!=s;v=p[v])//从汇点往回走
　　　　{
　　　　　　f[p[v]][v]+=a[t];//更新正向流量
　　　　　　f[v][p[v]]-=a[t];//更新反向流量
　　　　}
　　　　flow+=a[t];//更新从s流出的总流量
　　}
　　return flow;
}

int main()
{
　　int u,v,i,c,ans;
　　while(scanf("%d%d",&n,&m)!=EOF){
　　　　memset(cap,0,sizeof(cap));
　　　　memset(f,0,sizeof(f));
　　　　for(i=1;i<=n;i++){
　　　　　　scanf("%d%d%d",&u,&v,&c);
　　　　　　cap[u][v]+=c;//注意重边
　　　　}
　　　　ans=Edmond_Karp(1,m);
　　　　printf("%d\n",ans);
　　}
　　return 0;
}