BAOVE - Bảo vệ
Tác giả: flashmt
Ngôn ngữ: C++
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int oo = 1 << 29;
struct edge
{
int x, y, cap, flow;
};
struct Flow
{
int n, S, T;
vector < vector <int> > a;
vector <int> cur, d;
vector <edge> e;
Flow() {}
Flow(int _n, int _S, int _T)
{
n = _n; S = _S; T = _T;
a = vector < vector <int> >(n + 1);
cur = vector <int>(n + 1);
d = vector <int>(n + 1);
}
void addEdge(int x, int y, int _cap)
{
edge e1 = {x, y, _cap, 0};
edge e2 = {y, x, 0, 0};
a[x].push_back(e.size()); e.push_back(e1);
a[y].push_back(e.size()); e.push_back(e2);
}
int bfs()
{
queue <int> q;
for (int i = 1; i <= n; i++) d[i] = -1;
q.push(S); d[S] = 0;
while (!q.empty() && d[T] < 0)
{
int x = q.front(); q.pop();
for (int i = 0; i < int(a[x].size()); i++)
{
int id = a[x][i], y = e[id].y;
if (d[y] < 0 && e[id].flow < e[id].cap)
q.push(y), d[y] = d[x] + 1;
}
}
return d[T] >= 0;
}
int dfs(int x, int val)
{
if (!val) return 0;
if (x == T) return val;
for (; cur[x] < int(a[x].size()); cur[x]++)
{
int id = a[x][cur[x]], y = e[id].y;
if (d[y] != d[x] + 1) continue;
int pushed = dfs(y, min(val, e[id].cap - e[id].flow));
if (pushed)
{
e[id].flow += pushed;
e[id ^ 1].flow -= pushed;
return pushed;
}
}
return 0;
}
int maxFlow()
{
int res = 0;
while (bfs())
{
for (int i = 1; i <= n; i++) cur[i] = 0;
while (1)
{
int val = dfs(S, oo);
if (!val) break;
res += val;
}
}
return res;
}
int minCut()
{
maxFlow();
int res = 0;
for (int x = 1; x <= n; x++)
if (d[x] >= 0)
for (int i = 0; i < int(a[x].size()); i++)
{
int id = a[x][i], y = e[id].y;
if (d[y] < 0) res += e[id].cap;
}
return res;
}
};
int main()
{
int n, x, y, z;
cin >> n;
Flow u(n, n, 1);
while (scanf("%d%d%d", &x, &y, &z) == 3)
u.addEdge(x, y, z);
cout << u.minCut() << endl;
}