题目链接：
http://poj.org/problem?id=1273
#include<iostream> #include<cstdio> #include<iomanip> #include<cmath> #include<algorithm> #include<vector> #include<cstring> #include<queue> #include<map> #include<string> #include<stack> #define fi first #define se second #define INF 0x3f3f3f3f #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define pqueue priority_queue #define NEW(a,b) memset(a,b,sizeof(a)) const double pi=4.0*atan(1.0); const double e=exp(1.0); const int maxn=1e4+8; typedef long long LL; typedef unsigned long long ULL; const LL mod=1e9+7; const ULL base=1e7+7; using namespace std; struct node{ int to,nxt,v; }g[maxn]; int head[maxn],curedge[maxn],dis[maxn],cnt=0,n; void add(int x,int y,int v){ g[cnt].nxt=head[x]; g[cnt].to=y; g[cnt].v=v; head[x]=cnt++; } bool bfs(int s,int t){ memset(dis,INF,sizeof(dis)); dis[s]=0; queue<int> que; while(!que.empty()) {que.pop();} que.push(s); while(!que.empty()){ int k=que.front(); //cout<<k<<endl; que.pop(); int tt=head[k]; while(tt!=-1){ if(dis[g[tt].to]==INF&&g[tt].v>0){ dis[g[tt].to]=dis[k]+1; que.push(g[tt].to); } tt=g[tt].nxt; } } return dis[t]!=INF; } int dfs(int u,int t,int flow){ if(u==t) return flow; //cout<<u<<endl; int &i=curedge[u]; int delta=flow; while(i!=-1){ if(dis[g[i].to]==dis[u]+1){ int d=dfs(g[i].to,t,min(delta,g[i].v)); g[i].v-=d; g[i^1].v+=d; delta-=d; if(delta==0) break; } i=g[i].nxt; } return flow-delta; } int dinic(int s,int t){ int ans=0; while(bfs(s,t)){ for(int i=1;i<=t;i++){ curedge[i]=head[i]; } ans+=dfs(s,t,INF); } return ans; } int main(){ int s,t; s=1; while(~scanf("%d%d",&n,&t)){ int x,y,v; memset(head,-1,sizeof(head)); for(int i=1;i<=n;i++){ scanf("%d%d%d",&x,&y,&v); add(x,y,v);add(y,x,0); } //cout<<'a'<<endl; printf("%d ",dinic(s,t)); } }