Cod sursa(job #670144)

Utilizator Catah15Catalin Haidau Catah15 Data 28 ianuarie 2012 15:17:06
Problema Taramul Nicaieri Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

#define maxN 10010
#define maxNN 110

int N;
int A[maxN], B[maxN];
int ST[maxN], DR[maxN];
bool viz[maxN], M[maxNN][maxNN];


bool cupleaza (int nod)
{
	if (viz[nod]) return false;
	viz[nod] = true;
	
	for (int i = 1; i <= B[0]; ++ i)
	{
		if (A[nod] == B[i]) continue;
		if (M[A[nod]][B[i]]) continue;
		
		if (! DR[i] || cupleaza (DR[i]))
		{
			if (DR[i]) M[A[DR[i]]][B[i]] = false;
			
			ST[nod] = i;
			DR[i] = nod;
			
			M[A[nod]][B[i]] = true;
			
			return true;
		}
	}
	
	return false;
}


int main()
{
	freopen ("harta.in", "r", stdin);
	freopen ("harta.out", "w", stdout);
	
	scanf ("%d", &N);
	
	for (int i = 1; i <= N; ++ i)
	{
		int in, out;
		
		scanf ("%d %d", &in, &out);
		
		for (int t = 1; t <= in; ++ t) A[++ A[0]] = i;
		for (int t = 1; t <= out; ++ t) B[++ B[0]] = i;
	}
	
	bool ok = true;
	int cuplaj = 0;
	
	while (cuplaj < A[0])
	{
		ok = false;
		
		memset (viz, 0, sizeof (viz));
		
		for (int i = 1; i <= A[0]; ++ i)
			if (! ST[i] && cupleaza (i)) ++ cuplaj, ok = true;
	}
	
	printf ("%d\n", A[0]);
	
	for (int i = 1; i <= A[0]; ++ i)
		if (ST[i]) printf ("%d %d\n", A[i], B[ST[i]]);
	
	
	return 0;
}