Cod sursa(job #396603)

Utilizator DraStiKDragos Oprica DraStiK Data 15 februarie 2010 17:30:56
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <algorithm>
#include <queue>
using namespace std;

#define DIM 205

int c[DIM][DIM],f[DIM][DIM];
int n,s,d,flow;
queue <int> q;
int t[DIM];

void read ()
{
    int i,j,x,y;

    scanf ("%d",&n);
    s=0; d=2*n+1;
    for (i=1; i<=n; ++i)
        for (j=1; j<=n; ++j)
            if (i!=j)
                c[i][j+n]=1;
    for (i=1; i<=n; ++i)
    {
        scanf ("%d%d",&x,&y);
        c[s][i]=x;
        c[i+n][d]=y;
    }
}

int bf ()
{
    int nod,i;

    memset (t,-1,sizeof (t));
    for (q.push (s); !q.empty (); q.pop ())
    {
        nod=q.front ();
        for (i=s; i<=d; ++i)
            if (t[i]==-1 && c[nod][i]-f[nod][i]>0)
            {
                t[i]=nod;
                q.push (i);
            }
    }
    return t[d];
}

void solve ()
{
    int i,j,minim;

    for ( ; bf ()!=-1; )
		for (i=s; i<=d; ++i)
		    if (t[i]>=0 && c[i][d]-f[i][d]>0)
		    {
				minim=c[i][d]-f[i][d];
    			for (j=i; j!=s; j=t[j])
    				minim=min (minim,c[t[j]][j]-f[t[j]][j]);
                f[i][d]+=minim;
                f[d][i]-=minim;
    			for (j=i; j!=s; j=t[j])
                {
                    f[t[j]][j]+=minim;
                    f[j][t[j]]-=minim;
                }
                flow+=minim;
        	}
}

void print ()
{
    int i,j;

    printf ("%d\n",flow);
    for (i=1; i<=n; ++i)
        for (j=1; j<=n; ++j)
            if (f[i][j+n])
                printf ("%d %d\n",i,j);
}

int main ()
{
    freopen ("harta.in","r",stdin);
    freopen ("harta.out","w",stdout);

    read ();
    solve ();
    print ();

    return 0;
}