Cod sursa(job #2992)

Utilizator gigi_becaliGigi Becali gigi_becali Data 20 decembrie 2006 12:15:16
Problema Taramul Nicaieri Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <cstdio>
#define maxn 128

int in[maxn], out[maxn], a[maxn][maxn], x[maxn][maxn],n;
int viz[maxn];
void citire()
{
	freopen("harta.in", "r", stdin);
	scanf("%d\n", &n);
	for(int i=1;i<=n;i++) scanf("%d %d\n", &out[i], &in[i]);
}

void calcul()
{

	int i, j, k, p, max, MAX, nod;
	
	for(int t=1;t<=n;t++)
	{
		MAX=0; i=0;
		for(j=1;j<=n;j++) if(!viz[j] && MAX<out[j]) MAX=out[j], i=j;
		if(i==0) return;
		viz[i]=1;
		if(out[i])
		{
			
			p=out[i];
			for(j=1;j<=p;j++)
			{
				max=0;
				nod=0;
				for(k=1;k<=n;k++) if(i!=k && in[k] && !a[i][k] && max<in[k]) max=in[k], nod=k;
				
			
				if(nod==0) continue;
				a[i][nod]=1;
				a[nod][i]=1;
				x[i][nod]=1;
		//		printf("(%d %d %d %d)\n", in[nod], out[i], nod, i);
				in[nod]--;
				out[i]--;
			}
		}
	}
}

void last()
{
	int i, j, ok=1;
	
	//for(i=1;i<=n;i++) printf("%d %d\n", in[i], out[i]);
	while(1)
	{
		ok=1;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++) if( i!=j && in[i] && out[j]) { x[j][i]=1; in[i]--; out[j]--; ok=0;}
	if(ok) return ;

	}
}		

int main()
{
	citire();
	calcul();
	last();
	int i, j, nr=0;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++) if(x[i][j]) nr++;
		
		
		freopen("harta.out", "w", stdout);
		printf("%d\n", nr);
	for(i=1;i<=n;i++)
	
		for(j=1;j<=n;j++) if(x[i][j])printf("%d %d\n",i , j);	
		
	
	return 0;
}