Cod sursa(job #122583)

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

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

void ek()
{
	int i;
	do{
		for(i=1;i<=n+2;i++) viz[i]=0;
		if(bfs()) return;
	L[0]=n+2;
	lg=0;
	a=b=10000;
	while(L[lg]!=1)
	{
		lg++;
		L[lg]=abs(viz[L[lg-1]]);
		if(viz[L[lg-1]]>0)
			a=min(a,C[L[lg]][L[lg-1]]-F[L[lg]][L[lg-1]]);
		else if(viz[L[lg-1]]<0)
			b=min(b,F[L[lg-1]][L[lg]]);
	}
	v=min(a,b);
	for(i=lg;i>0;i--) if(viz[L[i-1]]>0) F[L[i]][L[i-1]]+=v;
	else
		if(viz[L[i-1]]<0) F[L[i]][L[i-1]]-=v;
	}
	while(1);
}

void afis()
{
	int i,j;
	for(i=2;i<=n+1;i++)
		for(j=2;j<=n+1;j++) if(F[i][j]) nr++;
	fprintf(g,"%d\n",nr);
	for(i=2;i<=n+1;i++)
		for(j=2;j<=n+1;j++)
			if(F[i][j])
			fprintf(g,"%d %d\n",i-1,j-1);
	//fprintf(g,"\n");
	/*fprintf(g,"%d\n",n);
	for(i=1;i<=n+2;i++)
		{
			for(j=1;j<=n+2;j++) fprintf(g,"%d ",F[i][j]);
			fprintf(g,"\n");
	}*/
	fclose(g);
}
int main()
{
	citire();
	ek();
	afis();
	return 0;
}