Cod sursa(job #122897)

Utilizator nuexistnuexist nuexist Data 13 ianuarie 2008 21:19:50
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include<stdio.h>
#define maxn 205
#define min(x,y) ((x)<(y)?(x):(y))
FILE *f=fopen("harta.in","r"), *g=fopen("harta.out","w");
int n,x,y,a,C[maxn][maxn],F[maxn][maxn],Q[maxn],viz[maxn],nr,L[maxn],lg;
void citire()
{
	fscanf(f,"%d",&n);
	int i,j;
	for(i=1;i<=n;i++) 
	{
		fscanf(f,"%d %d",&x,&y);
		C[1][i+1]=x;
		C[n+i+1][n+n+2]=y;
	}
	for(i=2;i<=n+1;i++)
		for(j=n+2;j<=2*n+1;j++) if((i+n)!=j) C[i][j]=1;
	fclose(f);
}

int bfs()
{
int p,u,x,i;
Q[0]=1;
p=u=0;
viz[1]=1;
while(p<=u && !viz[2*n+2])
{
x=Q[p++];
for(i=1;i<=2*n+2;i++)
if(!viz[i])
if(F[x][i]<C[x][i]) { viz[i]=x; Q[++u]=i;}
}
return !viz[2*n+2];
}

void ek()
{
int i;
do{
for(i=1;i<=2*n+2;i++) viz[i]=0;
if(bfs()) return;

L[0]=2*n+2;
lg=0;
a=10000;
while(L[lg]!=1)
{
lg++;
L[lg]=viz[L[lg-1]];
a=min(a,C[L[lg]][L[lg-1]]-F[L[lg]][L[lg-1]]);
}

for(i=lg;i>0;i--) 
{

F[L[i]][L[i-1]]+=a;
F[L[i-1]][L[i]]-=a;
}
}while(1);


}

void afis()
{
int i,j;
for(i=2;i<=n+1;i++)
for(j=2+n;j<=2*n+1;j++) if(F[i][j]) nr++;
fprintf(g,"%d\n",nr);
for(i=2;i<=n+1;i++)
for(j=2+n;j<=2*n+1;j++)
if(F[i][j])
fprintf(g,"%d %d\n",i-1,j-n-1);

fclose(g);
}
int main()
{
	citire();
	ek();
	afis();
	return 0;
}