# Cod sursa(job #2992)

Utilizator Data 20 decembrie 2006 12:15:16 Taramul Nicaieri 50 cpp done Arhiva de probleme 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;
}``````