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

Download