Cod sursa(job #573691)

Utilizator mottyMatei-Dan Epure motty Data 6 aprilie 2011 15:06:30
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <fstream>
#include <cstdlib>
#include <cstring>
#include <queue>

#define alt(x) (n + x) // nodul x.in

using namespace std;

ifstream in("harta.in");
ofstream out("harta.out");

const int N = 205;
const int Inf = 0x3f3f3f;

int n;
int d;
int edgeCount;
int fat[N];
int c[N][N];
int f[N][N];

bool viz[N];

void Read()
{
	in >> n;
	d = 2*n + 1; // Destinatie

	for (int i = 1; i <= n; ++i)
		in >> c[0][i] >> c[alt(i)][d]; // Cate drumuri intra in i si cate drumuri ies din i
}

void SetPossibleEdges()
{
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			if (i != j)
				c[i][alt(j)] = 1; // Poate exista 1 muchie intre i si j
}

bool Road()
{
	queue <int> q;
	memset(viz, 0, sizeof(viz));

	q.push(0);
	viz[0] = 1;

	while (!q.empty() && !viz[d])
	{
		int node = q.front();

		for (int next = 0; next <= d; ++next)
			if (!viz[next] && c[node][next] - f[node][next] > 0)
			{
				viz[next] = true;
				fat[next] = node;

				q.push(next);
			}

		q.pop();
	}

	return viz[d];
}

void GetMaxFlow()
{
	while (Road())
	{
		int node = d;
		int minFlow = Inf;

		while (node)
		{
			if (c[fat[node]][node] - f[fat[node]][node] < minFlow)
				minFlow = c[fat[node]][node] - f[fat[node]][node];

			node = fat[node];
		}

		node = d;

		while (node)
		{
			f[fat[node]][node] += minFlow;
			f[node][fat[node]] -= minFlow;

			node = fat[node];
		}

		edgeCount++;
	}
}

void PrintEdges()
{
	out << edgeCount << "\n";

	for (int i = 1; i <= n; ++i)
		if (c[0][i])
			for (int j = 1; j <= n; ++j)
				if (f[i][alt(j)])
					out << i << " " << j << "\n";
}

int main()
{
	Read();
	SetPossibleEdges();

	GetMaxFlow();

	PrintEdges();

	return 0;
}