Cod sursa(job #41736)

Utilizator andrei_infoMirestean Andrei andrei_info Data 28 martie 2007 15:26:27
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <stdio.h>
#define nmax 101
int fl[2*nmax+1][2*nmax+1], tata[2*nmax+1], lista[2*nmax+1], min[nmax],mout[nmax],n,m,sursa,dest;

void read();
void init();
void calc();
int bf();

int main()
{
read();
init();
calc();
return 0;
}

void read()
{
int i;
freopen("harta.in","r",stdin);
scanf("%d", &n);
for (i=1; i<=n; i++)
    {
    scanf("%d %d", &mout[i], &min[i]);
    m+=mout[i];
    }
fclose(stdin);
sursa=0; dest=2*n+1;
}

void init()
{
int i,j;
for (i=1; i<=n; i++)
    fl[sursa][i]=mout[i];
for (i=n+1; i<=2*n; i++)
    fl[i][dest]=min[i-n];
for (i=1; i<=n; i++)
    for (j=n+1; j<=2*n; j++)
        if (i != j-n)
           fl[i][j]=1;
        else         fl[i][j]=-1;
}

int bf()
{
int i,j,k=1;
for (i=sursa; i<=dest; i++)
    tata[i]=-1;
lista[1]=0; i=1;
tata[0]=0;
while (i<=k)
      {
      for (j=sursa; j<=dest; j++)
          if ( (fl[lista[i]][j] > 0) && (tata[j] ==-1) )
             {
             tata[j]=lista[i];
             k+=1;
             lista[k]=j;
	     if (j==dest) { i=k; break; }
             }
     i+=1;
     }
if (tata[dest] != -1) return 1;
else return 0;
}

void flux()
{
int i=dest,j;
while (i !=0)
      {
      j=tata[i];
      fl[j][i]-=1;
      fl[i][j]+=1;
      i=j;
      }
}

void calc()
{
int i,j;

while (bf() ==1 )
      flux();
freopen("harta.out","w",stdout);
printf("%d\n",m);
for (i=1; i<=n; i++)
   for (j=n+1; j<=2*n; j++)
       if (fl[i][j] ==0)
	  printf("%d %d\n",i,j-n);
fclose(stdout);
}