Cod sursa(job #320042)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 3 iunie 2009 12:27:05
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <stdio.h>

using namespace std;

#define maxn 1010

long n, i, m, j, k, a, b, x, l, r, pl, ss, ok, nod, sol, nd, c[maxn][maxn], up[maxn], f[maxn], coa[maxn];

long min(long a, long b)
{
    if(a>b) return b;
    return a;
}

int main()
{
    freopen("harta.in", "r", stdin);
    freopen("harta.out", "w", stdout);
    scanf("%d", &n);
    for(i=1; i<=n; i++)
    {
        scanf("%d %d", &pl, &ss);
        nd+=pl;
        c[1][i+1]=pl;
        c[i+n+1][2*n+2]=ss;
    }
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
        {
            if(i!=j) c[i+1][j+n+1]=1;
        }
    }
    n=n*2+2;
    ok=1;
    while(ok)
    {
        for(i=1; i<=n; i++)
        {
            f[i]=0;
            up[i]=-1;
        }
        f[1]=111100;
        coa[1]=1;
        for(l=1, r=1; l<=r; l++)
        {
            nod=coa[l];
            for(i=1; i<=n; i++)
            {
                if(f[i]==0 && c[nod][i]>0)
                {
                    f[i]=min(f[nod], c[nod][i]);
                    up[i]=nod;
                    r++;
                    coa[r]=i;
                }
            }
            if(f[n]>0) break;
        }
        nod=n;
        if(f[n]>0)
        {
            ok=1;
            sol+=f[n];
            while(up[nod]!=-1)
            {
                i=up[nod];
                c[nod][i]+=f[n];
                c[i][nod]-=f[n];
                nod=up[nod];
            }
        }        
        else ok=0;
    }
    n=n/2-1;
    printf("%d\n", nd);
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
        {
            if(i!=j && c[i+1][n+j+1]==0) printf("%d %d\n", i, j);
        }
    }
    return 0;
}