Cod sursa(job #88193)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 30 septembrie 2007 18:25:55
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
# include <stdio.h>

const long int MAXN=105;

long int tata[2*MAXN+1],n,muclen,source,dest,cd[2*MAXN+10],a[2*MAXN+1][2*MAXN+1];
struct {long int a,b;} muc[MAXN*MAXN+1];

void citire()
{
FILE *f=fopen("harta.in","r");
fscanf(f,"%ld",&n);
long int i,aa,bb,j;
source=0;
dest=2*n+1;
for (i=1;i<=n;i++)
	{
	fscanf(f,"%ld%ld",&aa,&bb);
	a[source][i]=aa;
	a[i+n][dest]=bb;
	}
for (i=1;i<=n;i++)
	for (j=1;j<=n;j++)
		if (i!=j) a[i][j+n]=1;
fclose(f);
}

void det_drum_min(long int source)
{
long int i,j;
cd[1]=source;
tata[1]=0;
tata[dest]=0;
long int prim=1,ultim=1,sel[2*MAXN+1]={0};
sel[source]=1;
while (prim<=ultim&&!tata[dest])
	{
	for (i=0;i<=2*n+1;i++)
		if (!sel[i]&&a[cd[prim]][i])
			{
			cd[++ultim]=i;
			tata[i]=cd[prim];
			sel[i]=1;
			}
	prim++;
	}
}

void satureaza(long int nod)
{
long int p=tata[nod];
while (nod)
	{
	a[p][nod]--;
	a[nod][p]++;
	nod=p;
	p=tata[nod];
	}
}

void flux()
{
do
	{
	det_drum_min(source);
	if (tata[dest]==0) break;
	satureaza(dest);
	}
while (1);
}

long int norm(long int a) {if(a>n) return a-=n;return a;}

void scrie()
{
long int nr=0,i,j;
FILE *g=fopen("harta.out","w");
for (i=1;i<=n;i++)
	for (j=n+1;j<=2*n;j++)
		if (a[j][i]) nr++;
fprintf(g,"%ld\n",nr);
for (i=1;i<=n;i++)
	for (j=n+1;j<=2*n;j++)
		if (a[j][i]) fprintf(g,"%ld %ld\n",norm(i),norm(j));
fcloseall();
}

int main()
{
citire();
flux();
scrie();
return 0;
}