Cod sursa(job #1966048)

Utilizator lflorin29Florin Laiu lflorin29 Data 14 aprilie 2017 20:46:09
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 212, INF = 1e9 + 2;

int src, dest, n, m, in[MAX_N], out[MAX_N], cap[MAX_N][MAX_N], vis[MAX_N], tata[MAX_N], f[MAX_N][MAX_N];
vector<int>g[MAX_N];

void bag(int x, int y, int c)
{
	cap[x][y] = c;
	g[x].push_back(y);
	g[y].push_back(x);
}

int opus(int x)
{
	return x > n ? x - n : x + n;
}

void Makegraph()
{
	for (int i = 1; i <= n; ++i)
	{
		bag(src, i, out[i]);
		bag(opus(i), dest, in[i]);
	}

	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			if (i == j)
				continue;
			bag(i, opus(j), 1);
			bag(j, opus(i), 1);
		}
	}
}

bool Bfs()
{
	memset(vis, 0, sizeof vis);
	memset(tata, 0, sizeof tata);
	queue<int>q;
	q.push(src);

	while (!q.empty())
	{
		int nod = q.front();
		q.pop();

		for (auto i : g[nod])
		{
			if (!vis[i] && cap[nod][i] - f[nod][i] > 0)
			{
				q.push(i);
				vis[i] = 1;
				tata[i] = nod;
			}
		}
	}
	return vis[dest];
}
int Increase()
{
	int mn = INF;

	for (int i = dest; i != src; i = tata[i])
		mn = min(mn, cap[tata[i]][i] - f[tata[i]][i]);
	for (int i = dest; i != src; i = tata[i])
	{
		f[tata[i]][i] += mn;
		f[i][tata[i]] -= mn;
	}

	return mn;
}

int Normal(int i)
{
	if (i > n)return i - n;

	return i;
}
void Fluxmaxim()
{
	int flow = 0;

	while (Bfs())
		flow += Increase();

	printf("%d\n", flow);

	for (int i = 1; i <= 2 * n; ++i)
	{
		for (int j = 1; j <= 2 * n; ++j)
		{
			if (f[i][j] > 0)
				printf("%d %d\n", Normal(i), Normal(j));
		}
	}

}

int main()
{
	freopen("harta.in", "r", stdin);
	freopen("harta.out", "w", stdout);

	scanf("%d", &n);
	src = 0, dest = 2 * n + 1;

	for (int i = 1; i <= n; ++i)
	{
		scanf("%d%d", &out[i], &in[i]);
	}

	Makegraph();
	Fluxmaxim();
}