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