BAOVE - Bảo vệ

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;

#define TR(v,i) for(typeof((v).begin()) i=(v).begin();i!=(v).end();++i)
const int N = 5005;
struct edge {
	int u, c, f;
	edge(){}
	edge(int u, int c): u(u), c(c), f(0) {}
};
vector<vector<edge> > g;
int n, s, t, trace[N];

void addEdge(int u, int v, int d) {
	TR(g[u], i) if(i->u == v) { i->c += d; return; }
	g[u].push_back(edge(v, d));
}
void addFlow(int u, int v, int d) { TR(g[u], i) if(i->u == v) { i->f += d; return; } }

void enter() {
	scanf("%d", &n); g.resize(n); s = n-1; t = 0;
	for(int u, v, d; scanf("%d%d%d",&u,&v,&d) == 3; ) {
		--u; --v;
		addEdge(u, v, d);
		addEdge(v, u, 0);
	}
}

int FindPath() {
	memset(trace, 0, sizeof trace); trace[s] = -1;
	queue<pair<int, int> > q; q.push(pair<int, int>(s, 1000000000));
	while(!q.empty()) {
		int u = q.front().first, f = q.front().second; q.pop();
		TR(g[u], i) if(trace[i->u] == 0 && i->c > i->f) {
			trace[i->u] = u;
			q.push(pair<int, int>(i->u, min(f, i->c - i->f)));
			if(i->u == t) return min(f, i->c - i->f);
		}
	}
	return -1;
}

void MaxFlow() {
	int res = 0;
	for(int inc; (inc = FindPath()) != -1; ) {
		res += inc; int v = t;
		do {
			int u = trace[v];
			addFlow(u, v, inc);
			addFlow(v, u, -inc);
			v = u;
		} while(v != s);
	}
	printf("%d\n", res);
}

int main() {
	enter();
	MaxFlow();
	return 0;
}

Download