Cod sursa(job #2987)

Utilizator gigi_becaliGigi Becali gigi_becali Data 20 decembrie 2006 11:39:41
Problema Taramul Nicaieri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 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=0x3f3f3f3f; 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=0x3f3f3f3f;
				nod=0;
				for(k=1;k<=n;k++) if(i!=k && in[k] && !a[i][k] && max>in[k]) max=in[k], nod=k;
				
			
					
				a[i][nod]=1;
				a[nod][i]=1;
				x[i][nod]=1;
				in[nod]--;
				out[i]--;
			}
		}
	}
}

int main()
{
	citire();
	calcul();
	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;
}