BAOVE - Bảo vệ
Tác giả: hieult
Ngôn ngữ: C++
#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
#define fi first
#define se second
#define PB push_back
#define MP make_pair
#define ep 0.00001
#define oo 1111111111
#define mod 1000000007
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define rep(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
//#define g 9.81
double const PI=4*atan(1.0);
using namespace std;
typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;
typedef long long ll;
void OPEN(){
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
}
// Dinic
#define maxn 5011
#define maxe 200011
struct Dinic{
int s, t, E, adj[maxe], cap[maxe], flow[maxe], next[maxe], last[maxn],
que[maxn], level[maxn], run[maxn];
void init(int _s, int _t){
s = _s; t = _t;
E = 0;
memset(last, -1, sizeof(last));
}
void add(int u, int v, int c1, int c2){
adj[E] = v; cap[E] = c1; flow[E] = 0; next[E] = last[u]; last[u] = E++;
adj[E] = u; cap[E] = c2; flow[E] = 0; next[E] = last[v]; last[v] = E++;
}
bool bfs(){
memset(level, -1, sizeof(level));
level[s] = 0;
int size = 0; que[size++] = s;
rep(i, size){
for(int u = que[i], e = last[u]; e != -1; e = next[e]){
int v = adj[e];
if(level[v] == -1 && flow[e] < cap[e]){
level[v] = level[u] + 1;
que[size++] = v;
}
}
}
return level[t] != -1;
}
int dfs(int u, int bot){
if(u == t) return bot;
for(int &e = run[u]; e != -1; e = next[e]){
int v = adj[e], delta;
if(level[v] == level[u] + 1 && flow[e] < cap[e] && (delta = dfs(v, min(bot, cap[e] - flow[e]))) > 0){
flow[e] += delta;
flow[e ^ 1] -= delta;
return delta;
}
}
return 0;
}
ll maxflow(){
ll total = 0;
while(bfs()){
memcpy(run, last, sizeof(last));
for(int delta = dfs(s, oo); delta > 0; delta = dfs(s, oo)) total += delta;
}
return total;
}
} dinic;
int main(){
//OPEN();
int n, u, v, cost;
scanf("%d", &n);
dinic.init(n, 1);
while(scanf("%d %d %d", &u, &v, &cost) > 0){
dinic.add(u,v,cost,0);
}
printf("%lld\n",dinic.maxflow());
}