Cod sursa(job #42250)

Utilizator sealTudose Vlad seal Data 28 martie 2007 23:53:09
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include<stdio.h>
#define Nm 101
#define Inf Nm*Nm
#define min(a,b) ((a)<(b)?(a):(b))
int C[2*Nm][2*Nm],F[2*Nm][2*Nm],De[Nm],Di[Nm],n;
int X[Nm*Nm],Y[Nm*Nm],m;
int Q[2*Nm],M[2*Nm],Pre[2*Nm];

void read()
{
    int i;

    freopen("harta.in","r",stdin);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
	scanf("%d%d",De+i,Di+i);
}

int BFS()
{
    int l,r,x,i;

    Q[l=r=0]=0;
    Pre[0]=-2;
    M[0]=Inf;
    for(i=1;i<=2*n+1;i++)
	Pre[i]=-1;

    while(l<=r && Pre[2*n+1]==-1)
    {
	x=Q[l++];
	for(i=1;i<=2*n+1;i++)
	    if(Pre[i]==-1 && F[x][i]<C[x][i])
	    {
		Pre[i]=x;
		M[i]=min(M[x],C[x][i]-F[x][i]);
		Q[++r]=i;
	    }
    }

    return Pre[2*n+1]!=-1;
}

void solve()
{
    int i,j;

    for(i=1;i<=n;i++)
    {
	C[0][i]=De[i];
	C[n+i][2*n+1]=Di[i];
	for(j=n+1;j<=2*n;j++)
	    C[i][j]=1;
	C[i][n+i]=0;
    }

    while(BFS())
    {
	i=2*n+1;
	while(i)
	{
	    F[Pre[i]][i]+=M[2*n+1];
	    F[i][Pre[i]]-=M[2*n+1];
	    i=Pre[i];
	}
    }

    m=0;
    for(i=1;i<=n;i++)
	for(j=n+1;j<=2*n;j++)
	    if(F[i][j])
	    {
		X[m]=i;
		Y[m++]=j-n;
	    }
}

void write()
{
    int i;

    freopen("harta.out","w",stdout);
    printf("%d\n",m);
    for(i=0;i<m;i++)
	printf("%d %d\n",X[i],Y[i]);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}