Cod sursa(job #479499)

Utilizator darrenRares Buhai darren Data 24 august 2010 11:41:06
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <cstring>
#include <fstream>
#include <utility>
#include <queue>

using namespace std;

void Read();
void Solve();
bool FindPath();
void Augment();
void Write();

int n;
int c[202][202], f[202][202], t[202];
bool s[202];
queue<int> q;
int tot;

int main()
{
	Read();
	Solve();
	Write();
}

void Read()
{
	ifstream fin("harta.in");
	fin >> n;
	for (int i = 1, g1, g2; i <= n; ++i)
	{
		fin >> g1 >> g2;
		c[0][i] = g1;
		c[i + n][2 * n + 1] = g2;

		tot += g1;
	}
	fin.close();
}

void Solve()
{
	for (int i = 1; i <= n; ++i)
		for (int j = n + 1; j <= 2 * n; ++j)
			if (i != j - n)
				c[i][j] = 1;
	while (FindPath())
		Augment();
}

bool FindPath()
{
	memset(s, 0, sizeof(s));
	while (!q.empty()) q.pop();
	q.push(0);
	s[0] = true;

	while (!q.empty())
	{
		int i = q.front(); q.pop();
		for (int j = 1; j <= 2 * n + 1; ++j)
			if (!s[j])
				if (f[i][j] < c[i][j])
				{
					t[j] = i;
					s[j] = true;
					if (j == 2 * n + 1) return true;
					q.push(j);
				}
	}
	return false;
}

void Augment()
{
	int i, j;
	for (i = 2 * n + 1, j = t[2 * n + 1]; i != 0; i = t[i], j = t[j])
		++f[j][i], --f[i][j];
}

void Write()
{
	ofstream fout("harta.out");
	fout << tot << '\n';
	for (int i = 1; i <= n; ++i)
		for (int j = n + 1; j <= 2 * n; ++j)
			if (f[i][j])
				fout << i << ' ' << j - n << '\n';
	fout.close();
}