Cod sursa(job #564205)

Utilizator dacyanMujdar Dacian dacyan Data 26 martie 2011 21:43:27
Problema Taramul Nicaieri Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <fstream>
#include <queue>
#include <vector>
#define DIM 101
using namespace std;

int n, m;
int c[DIM][DIM], f[DIM][DIM];
int ge[DIM], gi[DIM];
int S, D;
vector<int> t;
vector<pair<int,int> > sol;

void Read();
void EK();
void Augment();
bool BF();
void Write();
void Build();

int main()
{
	Read();
	Build();
	EK();
	Write();
	return 0;
}

void Read()
{
	ifstream fin("harta.in");
	fin >> n;
	for (int i = 1; i <= n; ++i)
		fin >> ge[i] >> gi[i];
	fin.close();
}

void Build()
{
	S = 0; D = 2 * n + 1;
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= n; ++j)
			if (i != j) c[i][j+n] = 1;
		c[S][i] = ge[i];
		c[i+n][D] = gi[i];
	}
}

void EK()
{
	while (BF())
		Augment();
	
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			if (i != j && f[i][j+n])
			{
				sol.push_back(make_pair(i,j));
				m++;
			}
}

bool BF()
{
	queue<int> Q;
	vector<bool> s(D+1);
	t.clear(); t.resize(D+1);
	s[S] = 1;
	Q.push(S);
	while (!Q.empty())
	{
		int i = Q.front();
		Q.pop();
		for (int j = S; j <= D; ++j)
		{
			if (s[j]) continue;
			if (f[i][j] < c[i][j])
			{
				s[j] = true;
				t[j] = i;
				Q.push(j);
				if (j == D) return true;
			}
		}
	}
	return false;
}

void Augment()
{
	int i, j;
	j = D;
	while (j != S)
	{
		i = t[j];
		f[i][j]++;
		f[j][i]--;
		j = i;
	}
}

void Write()
{
	ofstream fout("harta.out");
	fout << m << '\n';
	for (int i = 0; i < m; ++i)
		fout << sol[i].first << ' ' << sol[i].second << '\n';
	fout.close();
}