Cod sursa(job #16894)

Utilizator devilkindSavin Tiberiu devilkind Data 14 februarie 2007 14:43:48
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <stdio.h>
#include <string.h>
#define NMAX 300

struct lista{long int nod;
             lista *urm;} *vf[NMAX];
          
FILE *h = fopen("harta.in","rt"), *g = fopen("harta.out","wt");
          
long int c[NMAX][NMAX],f[NMAX][NMAX],i,j,k,n,gext[NMAX],gint[NMAX],m,st[NMAX],fmin,marc[NMAX];

void citire()
{
fscanf(h,"%ld",&n);
lista *p;
for (i=1;i<=n;i++)
    {fscanf(h,"%ld %ld",&gint[i],&gext[i]);
    c[0][i]=gint[i];
    c[i][0]=0;
    c[n+i][2*n+1]=gext[i];
    c[2*n+1][n+1]=0;
    m+=gint[i];
    
    p=new lista;
    p->nod=0;
    p->urm=vf[i];
    vf[i]=p;
    
    p=new lista;
    p->nod=i;
    p->urm=vf[0];
    vf[0]=p;
    
    p=new lista;
    p->nod=2*n+1;
    p->urm=vf[n+i];
    vf[n+i]=p;
    
    p=new lista;
    p->nod=n+i;
    p->urm=vf[2*n+1];
    vf[2*n+1]=p;

    }
long int x,y;
for (i=1;i<=n;i++)
	for (j=1;j<=n;j++)
	    if (j!=i)
		{x=i;y=n+j;

		p=new lista;
		p->nod=x;
		p->urm=vf[y];
		vf[y]=p;

		p=new lista;
		p->nod=y;
		p->urm=vf[x];
		vf[x]=p;
		c[x][y]=1;
		c[y][x]=0;
		}
fprintf(g,"%ld\n",m);
}

long int DF(long int nod)
{
long int ok=0;
lista *p;
marc[nod]=1;
st[++k]=nod;
if (nod==2*n+1) return 1;
p=vf[nod];
while (p)
      {
       if ((!marc[p->nod])&&(f[nod][p->nod]<c[nod][p->nod])) {ok=DF(p->nod);
                                                             if (ok) return 1;
                                                             }
       p=p->urm;
       }
k--;
return 0;    
}

void solve()
{
//porneste fluxu si afiseaza muchiile :D
long int ok=1;
while (ok)
      {
      k=0;
      memset(marc,0,sizeof(marc));
      ok=DF(0);
      if (ok)
	 {fmin=100000;
         for (i=1;i<=k-1;i++)
             if (c[st[i]][st[i+1]] - f[st[i]][st[i+1]] < fmin) fmin=c[st[i]][st[i+1]] - f[st[i]][st[i+1]];
         for (i=1;i<=k-1;i++)
             {f[st[i]][st[i+1]]+=fmin;
             f[st[i+1]][st[i]]-=fmin;}
         }   
      }
for (i=1;i<=2*n;i++)
    for (j=n+1;j<=2*n;j++)
        if (f[i][j]==1) fprintf(g,"%ld %ld\n",i,j-n);
}

int main()
{
citire();
solve();
fclose(h);
fclose(g);
return 0; 
}