Cod sursa(job #190195)

Utilizator crusRus Cristian crus Data 20 mai 2008 17:41:29
Problema Taramul Nicaieri Scor 10
Compilator c Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <stdio.h>
#define input "harta.in"
#define output "harta.out"
#define nmax 101
#define maxim 300
int n,m,c[nmax][nmax],f[nmax][nmax],v[nmax],cap,coada,t[nmax],d[nmax][nmax];
int fm=0;
void citire()
{
 int i,x,y;
 freopen(input,"r",stdin);
 scanf("%d",&n);
 for (i=1;i<=n;i++)
     {
      scanf("%d %d",&x,&y);
      c[0][i]=x;
      c[n+i][n+n+1]=y;
     }
}
int bfs()
{
 int i,j,fol[nmax],nod;
 cap=1,coada=1;
 v[cap]=0;
 for (i=1;i<=n+n+1;i++) fol[i]=0;
 fol[0]=1;
 while (cap<=coada)
       {
	nod=v[cap];
	for (i=1;i<=n+n+1;i++)
	    if (c[nod][i]-f[nod][i]>0 && fol[i]==0)
	       {
		coada++;
		v[coada]=i;
		t[i]=nod;
		fol[i]=1;
	       }
	cap++;
       }
 return fol[n+n+1];
}
int min(int a,int b)
{
 if (a<b) return a;
 return b;
}
void solve()
{
 int i,j,flux,u;
 for (i=1;i<=n;i++)
     for (j=n+1;j<=n+n;j++)
	 if (i+n!=j)
	    if (c[j][n+n+1]) c[i][j]=1;
 for (i=n+1;i<=n+n;i++)
     for (j=1;j<=n;j++)
	 if (i!=j+n)
	    if (c[0][j]) c[i][j]=1;
 i=i;
 while (bfs())
       {
	flux=maxim;
	for (u=n+n+1;u;u=t[u])
	    flux=min(flux,c[t[u]][u]-f[t[u]][u]);
	for (u=n+n+1;u;u=t[u])
	    {
	     f[t[u]][u]+=flux;
	     f[u][t[u]]-=flux;
	    }
	fm++;
       }
}
void afisare()
{
 int i,j;
 freopen(output,"w",stdout);
 printf("%d\n",fm);
 for (i=1;i<=n;i++)
     for (j=n+1;j<=n+n;j++)
	 if (f[i][j]>0)
	    printf("%d %d\n",i,j-n);
}
int main()
{
 citire();
 solve();
 afisare();
 return 0;
}