POJ_3469_sap.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];

Edge *E[MAXN], *cur[MAXN], *cnt;
int pre[MAXN], dis[MAXN], gap[MAXN];
int N, M, S, T, NN;


bool get(int& tmp)
{
	char ch;
	int flag = 0;
    tmp = 0;
	for (ch = getchar(); ch < 48 || ch > 57; ch = getchar())
	if (ch == int('-')||ch==EOF) break;
	if (ch==EOF) return 0;
	if (ch == int('-')) flag = 1; else tmp = int(ch) - 48;
	for (ch = getchar(); 48 <= ch && ch <= 57; ch = getchar())
	tmp = tmp * 10 + int(ch) - 48;
    return 1;
	//return (flag) ? -tmp : tmp;
}

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];
}

int sap() {
	int maxflow=0, aug=inf, u, v;
	for (int i=0; i<NN; i++) cur[i]=E[i], gap[i]=dis[i]=0;
	gap[S]=NN; u=pre[S]=S;
	while (dis[S]<NN) {
		bool flag=false;
		for (Edge *&p=cur[u]; p; p=p->next) 
			if (p->flow>0 && dis[u]==dis[v=p->v]+1) {
				flag=true;
				if (p->flow<aug) aug=p->flow;
				pre[v]=u; u=v;
				if (u==T) {
					maxflow+=aug;
					while (u!=S) {
						u=pre[u];
						cur[u]->flow-=aug;
						cur[u]->op->flow+=aug;
					}
					aug=inf;
				}
				break;
			}
		if (flag) continue;
		int mindis=NN;
		for (Edge *p=E[u]; p; p=p->next) 
			if (p->flow>0 && dis[p->v]<mindis) {
				mindis=dis[p->v]; cur[u]=p;
			}
		if ((--gap[dis[u]])==0) break;
		gap[dis[u]=mindis+1]++; u=pre[u];
	}
	return maxflow;
}

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

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