Cod sursa(job #219535)

Utilizator AndreyPAndrei Poenaru AndreyP Data 7 noiembrie 2008 11:39:32
Problema Taramul Nicaieri Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include<stdio.h>
#include<string.h>
#define INF 1<<30
#define N 205
int n,s,d,m;
struct ajt
{
	int x,y;
};
ajt v[5052];
int c[N][N],f[N][N],t[N],flux;
inline int min(int x,int y)
{
	return x<y ? x : y;
}
void citire()
{
	int x,y,j;
	for(int i=1; i<=n; i++)
	{
		scanf("%d%d",&x,&y);
		c[0][i]=x;
		c[i+n][d]=y;
		for(j=1; j<=n; j++)
		{
			if(j==i)
				continue;
			c[i][j+n]=1;
		}
	}
}
bool bfs()
{
	int p,u,nod,i,q[N];
	memset(t,0,sizeof(t));
	p=u=0;
	q[0]=s;
	t[s]=-1;
	for(; p<=u; p++)
	{
		nod=q[p];
		for(i=0; i<=d; i++)
		{
			if(!t[i] && c[nod][i]>f[nod][i])
			{
				q[++u]=i;
				t[i]=nod;
				if(i==d)
					return true;
			}
		}
	}
	return false;
}
int main()
{
	freopen("harta.in","r",stdin);
	freopen("harta.out","w",stdout);
	scanf("%d",&n);
	d=(n<<1)+1;
	citire();
	int r,i,j;
	for(flux=0; bfs(); flux+=r)
	{
		r=INF;
		i=d;
		while(i!=s)
		{
			r=min(r,c[t[i]][i]-f[t[i]][i]);
			i=t[i];
		}
		i=d;
		while(i!=s)
		{
			f[t[i]][i]+=r;
			f[i][t[i]]-=r;
			i=t[i];
		}
	}
	for(i=1; i<=n; i++)
	{
		for(j=n+1; j<d; j++)
		{
			if(f[i][j]>0)
			{
				v[m].x=i;
				v[m].y=j-n;
				m++;
			}
		}
	}
	/*for(i=1; i<=n; i++)
	{
		for(j=n+1; j<d; j++)
			printf("%d ",f[i][j]);
		printf("\n");
	}*/
	printf("%d\n",m);
	for(i=0; i<m; i++)
		printf("%d %d\n",v[i].x,v[i].y);
	//printf("\n");
	/*for(i=1; i<=n; i++)
		printf("%d ",c[0][i]);
	printf("\n");
	for(i=1; i<=n; i++)
		printf("%d ",c[i+n][d]);
	printf("\n");*/
	return 0;
}