题目链接：http://poj.org/problem?id=3469
#include <cstdio> #include <cmath> #include <algorithm> #include <iostream> #include <cstring> #include <queue> #include <vector> #define maxn 23000 #define maxe 242000 using namespace std; const int INF = 0x3f3f3f; struct Edge{ int from,to,cap,flow; int next; }; struct Dinic{ int s,t; int head[maxn]; int cur[maxn]; Edge edges[2*maxe]; int d[maxn]; bool vis[maxn]; int cnt; void init(){ memset(head,-1,sizeof(head)); cnt = 0; } void addedge(int from,int to,int cap,int cap2){ edges[cnt].from = from; edges[cnt].to = to; edges[cnt].cap = cap; edges[cnt].flow = 0 ; edges[cnt].next = head[from]; head[from] = cnt++; edges[cnt].from = to ; edges[cnt].to = from; edges[cnt].cap = cap2; edges[cnt].flow = 0 ; edges[cnt].next = head[to]; head[to] = cnt++; } bool bfs(){ memset(vis,0,sizeof(vis)); queue<int> Q; Q.push(s); vis[s] = true; d[s] = 0; while(!Q.empty()){ int u = Q.front(); Q.pop(); for(int i=head[u];i!=-1;i=edges[i].next){ Edge& e = edges[i]; if(!vis[e.to] && e.cap>e.flow){ vis[e.to] = true; d[e.to] = d[e.from] + 1; Q.push(e.to); } } } return vis[t]; } int dfs(int u,int res){ if( u == t || res == 0) return res; int flow = 0,f; for(int& i=cur[u];i!=-1;i=edges[i].next){ Edge& e = edges[i]; if(d[e.to] == d[e.from] + 1 && (f = dfs(e.to,min(res,e.cap-e.flow)))>0){ e.flow += f; edges[i^1].flow -= f; flow += f; res -= f; if(res == 0) break; } } return flow; } int Maxflow(int S,int T){ s = S; t = T; int flow = 0; while(bfs()){ for(int i=s;i<=t;i++) cur[i] = head[i]; flow += dfs(s,INF); } return flow; } }solver; int main() { //if(freopen("input.txt","r",stdin)== NULL) {printf("Error "); exit(0);} int N,M; while(scanf("%d%d",&N,&M) != EOF){ solver.init(); int s,t; s = 0; t = N + 1; for(int i=1;i<=N;i++){ int a,b; scanf("%d%d",&a,&b); solver.addedge(s,i,a,0); solver.addedge(i,t,b,0); } for(int i=1;i<=M;i++){ int a,b,w; scanf("%d %d %d",&a,&b,&w); solver.addedge(a,b,w,w); } printf("%d ",solver.Maxflow(s,t)); } return 0; }