POJ_3469_dinic.cpp

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=20010;
const int MAXM=600000;
const int inf=1000000000;

struct Edge {
	int v, flow;
	Edge *next, *op;
}mem[MAXM], *E[MAXN], *cnt;

int level[MAXN], Q[MAXN];
int N, M, S, T;

inline void addedge(int u, int v, int a, int b) {
	cnt->v=v; cnt->flow=a; cnt->next=E[u]; E[u]=cnt++;
	cnt->v=u; cnt->flow=b; cnt->next=E[v]; E[v]=cnt++;
	E[u]->op=E[v]; E[v]->op=E[u];
}

bool dinic_bfs() {
	memset(level, -1, sizeof(level));
	level[S]=0; Q[0]=S;
	for (int h=0, t=1; h<t; h++) {
		int u=Q[h], v;
		for (Edge *p=E[u]; p; p=p->next) 
			if (level[v=p->v]==-1 && p->flow>0) {
				level[v]=level[u]+1;
				Q[t++]=v;
			}
	}
	return (level[T]!=-1);
}

int dinic_dfs(int u, int low) {
	if (u==T) return low;
	int ret=0, tmp, v;
	for (Edge *p=E[u]; p && ret<low; p=p->next) 
		if (level[v=p->v]==level[u]+1 && p->flow>0) {
			if (tmp=dinic_dfs(v, min(low-ret, p->flow))) {
				ret+=tmp, p->flow-=tmp, p->op->flow+=tmp;
			}
		}
	if (!ret) level[u]=-1; return ret;
}

int dinic() {
	int maxflow=0, t;
	while (dinic_bfs()) {
		while (t=dinic_dfs(S, inf)) maxflow+=t;
	}
	return maxflow;
}

void init() {
	memset(E, 0, sizeof(E));
	S=0; T=N+1; cnt=mem;
}

int main() {
	int a, b, c;
	scanf("%d%d", &N, &M);
	init();
	for (int i=1; i<=N; i++) {
		scanf("%d%d", &a, &b);
		addedge(S, i, a, 0);
		addedge(i, T, b, 0);
	}
	while (M--) {
		scanf("%d%d%d", &a, &b, &c);
		addedge(a, b, c ,c);
	}
	printf("%d\n", dinic());
	return 0;
}