Cod sursa(job #423825)

Utilizator Andrei_ScorpioAndreiana Andrei Daniel Andrei_Scorpio Data 24 martie 2010 12:39:42
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
#include<stdio.h>
#include<string.h>
#define Nmax 210
int n,cap[Nmax][Nmax],fl[Nmax][Nmax],S,D,viz[Nmax],c[Nmax],t[Nmax],nrt;
struct nod
{
	int inf;
	nod *urm;
}*a[Nmax];
void citire()
{
	int i,x,y;
	nod *p;
	for(i=1;i<=n;i++)
	{
		scanf("%d %d",&x,&y);
		p=new nod;
		p->inf=i;
		cap[S][i]=x;
		p->urm=a[S];
		a[S]=p;
		p=new nod;
		p->inf=S;
		p->urm=a[i];
		a[i]=p;
		p=new nod;
		p->inf=D;
		cap[i+n][D]=y;
		p->urm=a[i+n];
		a[i+n]=p;
		p=new nod;
		p->inf=i+n;
		p->urm=a[D];
		a[D]=p;
		nrt+=x;
	}
}
int BFS()
{

 memset(viz,0,sizeof(viz));
 c[1]=S;
 viz[S]=1;
 int p,u;
 p=u=1;
 nod *pp;
 while(p<=u)
 {
	if(c[p]!=D)
		for(pp=a[c[p]];pp!=NULL;pp=pp->urm)
			if(viz[pp->inf]==0 && cap[c[p]][pp->inf]>fl[c[p]][pp->inf])
			{
				u++;
				c[u]=pp->inf;
				viz[pp->inf]=1;
				t[pp->inf]=c[p];
			}
	p++;
 }
 return viz[D];
}

int main()
{
	freopen ("harta.in","r",stdin);
	freopen ("harta.out","w",stdout);
	scanf("%d",&n);
	S=0;
	D=2*n+1;
	nod *p;
	int i,j,minim;
	citire();
	for(i=1;i<=n;i++)
		for(j=n+1;j<=2*n;j++)
			if(i!=j-n)
			{
				p=new nod;
				p->inf=j;
				p->urm=a[i];
				a[i]=p;
				p=new nod;
				p->inf=i;
				p->urm=a[j];
				a[j]=p;
				cap[i][j]=1;
			}
	printf("%d\n",nrt);
	while(BFS())
	{
		for(p=a[D];p!=NULL;p=p->urm)
		{
			if(cap[p->inf][D]-fl[p->inf][D]>0 && viz[p->inf])
			{
				minim=cap[p->inf][D]-fl[p->inf][D];
				int aj;
				aj=p->inf;
				while(aj!=S)
				{
					if(minim>cap[t[aj]][aj]-fl[t[aj]][aj])
						minim=cap[t[aj]][aj]-fl[t[aj]][aj];
					aj=t[aj];
				}
				if(minim==0)	continue;
				fl[p->inf][D]+=minim;
				fl[D][p->inf]-=minim;
				aj=p->inf;
				while(aj!=S)
				{
					fl[t[aj]][aj]+=minim;
					fl[aj][t[aj]]-=minim;
					
					aj=t[aj];
				}
			}
		}
	}
	//printf("\n\n");
for(i=1;i<=n;i++)
		for(j=n+1;j<=2*n;j++)
			if(fl[i][j]==1)
				printf("%d %d\n",i,j-n);

	return 0;
}