Cod sursa(job #496971)

Utilizator ooctavTuchila Octavian ooctav Data 31 octombrie 2010 19:04:25
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.13 kb
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

const int INF = 1000000000;
const int NMAX = 105;

int N, MCH;
int coada[NMAX * NMAX], tata[NMAX * NMAX];
vector<int> V[2 * NMAX];
int C[2 * NMAX][2 * NMAX];
int F[2 * NMAX][2 * NMAX];
pair<int, int> grad[NMAX];
pair<int, int> M[NMAX * NMAX];

void citire()
{
	scanf("%d",&N);
	for(int i = 1; i <= N ; i++)
		scanf("%d %d", &grad[i].first, &grad[i].second);
}

void face_muchii()
{
	for(int i = 1 ; i <= N ; i++)
	{
		V[0].push_back(i);
		V[i].push_back(0);
		C[0][i] = grad[i].first;
	}
	
	for(int i = 1 ; i <= N ; i ++)
		for(int j = N + 1 ; j <= 2 * N ; j++)
			if(i + N != j)
			{
				V[i].push_back(j);
				V[j].push_back(i);
				C[i][j] = 1;
			}
	
	for(int i = N + 1 ; i <= 2 * N ; i++)
	{
		V[2 * N + 1].push_back(i);
		V[i].push_back(2 * N + 1);
		C[i][2 * N + 1] = grad[i - N].second;
	}
}

bool BFS()
{
	bool viz[2 * NMAX] = {0};
	fill(coada, coada + 2 * NMAX, 0);
	
	coada[++coada[0]] = 0;
	
	for(int i = 1 ; i <= coada[0] ; i++)
	{
		for(vector<int> :: iterator it = V[coada[i]].begin() ; it != V[coada[i]].end() ; it++)
			if(F[coada[i]][*it] < C[coada[i]][*it] && !viz[*it])
			{
				tata[*it] = coada[i];
				if(*it == 2 * N + 1)
					return 1;
				coada[++coada[0]] = *it;
				viz[*it] = 1;
			}			
	}
	
	return 0;
}

void flux()
{
	while(BFS())
	{
		int min_flow = INF;
		for(int i = 2 * N + 1 ; i ; i = tata[i])
			min_flow = min(min_flow, C[tata[i]][i] - F[tata[i]][i]);
		
		for(int i = 2 * N + 1 ; i ; i = tata[i])
		{
			F[tata[i]][i] += min_flow;
			F[i][tata[i]] -= min_flow;
		}
	}
}

void numara_muchii()
{
	for(int i = 1 ; i <= N ; i ++)
		for(int j = N + 1 ; j <= 2 * N ; j++)
			if(F[i][j] == 1)
			{
				M[++MCH].first = i;
				M[MCH].second = j - N;
			}
}

void scrie()
{
	printf("%d\n", MCH);
	for(int i = 1 ; i <= MCH ; i++)
		printf("%d %d\n", M[i].first, M[i].second);
}

int main()
{
	freopen("harta.in","r",stdin);
	freopen("harta.out","w",stdout);
	citire();
	face_muchii();
	flux();
	numara_muchii();
	scrie();

	return 0;
}