Cod sursa(job #180631)

Utilizator M@2Te4iMatei Misarca M@2Te4i Data 17 aprilie 2008 12:19:04
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <cstdio>
#define nmax 101

int fl[2*nmax+1][2*nmax+1], tata[2*nmax+1], lista[2*nmax+1], min[nmax],mout[nmax],n,m,sursa,dest;

void read()
{
    int i;
    freopen("harta.in","r",stdin);
    scanf("%d", &n);
    for (i=1; i<=n; i++)
    {
        scanf("%d%d", &mout[i], &min[i]);
        m+=mout[i];
    }
    fclose(stdin);
    sursa=0;
    dest=2*n+1;
}

void init()
{
    int i,j;
    for (i=1; i<=n; i++)
        fl[sursa][i]=mout[i];
    for (i=n+1; i<=2*n; i++)
        fl[i][dest]=min[i-n];
    for (i=1; i<=n; i++)
        for (j=n+1; j<=2*n; j++)
            if (i!=j-n)
                fl[i][j]=1;
            else
                fl[i][j]=-1;
}

int bf()
{
    int i,j,k=1;
    for (i=sursa; i<=dest; i++)
        tata[i]=-1;
    lista[1]=0; i=1;
    tata[0]=0;
    while (i<=k)
    {
        for (j=sursa; j<=dest; j++)
            if (fl[lista[i]][j]>0 && tata[j] ==-1)
            {
                tata[j]=lista[i];
                k+=1;
                lista[k]=j;
                if (j==dest)
                {
                    i=k;
                    break;
                }
            }
        i+=1;
    }
    if (tata[dest]!=-1)
        return 1;
    else
        return 0;
}

void flux()
{
    int i=dest,j;
    while (i !=0)
    {
        j=tata[i];
        fl[j][i]-=1;
        fl[i][j]+=1;
        i=j;
    }
}

void calc()
{
    while (bf() ==1 )
        flux();
    freopen("harta.out","w",stdout);
    printf("%d\n",m);
    for (int i=1; i<=n; i++)
        for (int j=n+1; j<=2*n; j++)
            if (fl[i][j]==0)
                printf("%d %d\n",i,j-n);
    fclose(stdout);
}

int main()
{
    read();
    init();
    calc();
    return 0;
}