Cod sursa(job #407474)

Utilizator jupanubv92Popescu Marius jupanubv92 Data 2 martie 2010 13:03:06
Problema Taramul Nicaieri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include<stdio.h>
#include<string.h>
#define Nmx 101

int n,gri[Nmx],viz[Nmx],gre[Nmx];
int l[Nmx][Nmx],r[Nmx][Nmx];

void citire()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d%d",&gre[i],&gri[i]);
}

int pairup(int nod)
{
	if(viz[nod])
		return 0;
	viz[nod]=1;
	for(int i=1;i<=n;++i)
		if(i!=nod&&r[i][0]<gri[i])
		{
			r[i][++r[i][0]]=nod;
			l[nod][++l[nod][0]]=i;
			return 1;
		}
	for(int i=1;i<=n;++i)
		for(int j=1;j<=r[i][0];++j)
			if(pairup(r[i][j]))
			{
				r[i][++r[i][0]]=nod;
				l[nod][++l[nod][0]]=i;
				return 1;
			}
	return 0;
}

void solve()
{
	int cuplaj=0,ok=0;
	do
	{
		ok=0;
		memset(viz,0,sizeof(viz));
		for(int i=1;i<=n;++i)
			if(l[i][0]<gre[i]&&pairup(i))
			{
				cuplaj++;
				ok=1;
			}
	}while(ok);
	printf("%d\n",cuplaj);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=l[i][0];++j)
			printf("%d %d\n",i,l[i][j]);
		
}

int main()
{
	freopen("harta.in","r",stdin);
	freopen("harta.out","w",stdout);
	citire();
	solve();
	return 0;
}