Cod sursa(job #748648)

Utilizator MagnvsDaniel Constantin Anghel Magnvs Data 14 mai 2012 13:33:18
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <stdio.h>
#include <vector>

using namespace std;

int c[256][256],f[256][256],v[256],q[256],p[256],n,s;
vector <int> g[256];

int bfs()
{
    int i,j,a,b;
    for (i=2;i<=n;++i) v[i]=0;
    v[1]=1;q[0]=1;q[1]=1;
    for (i=1;i<=q[0];++i)
    {
        a=q[i];
        if (a!=n)
            for (j=0;j<g[a].size();++j)
            {
                b=g[a][j];
                if ((c[a][b]>f[a][b])&&(!v[b]))
                {
                    ++q[0];
                    q[q[0]]=b;
                    p[b]=a;
                    v[b]=1;
                }
            }
    }
    return v[n];
}

int main()
{
    int i,j,x,y,a,t;
    freopen("harta.in","r",stdin);
    freopen("harta.out","w",stdout);
    scanf("%d",&n);
    for (i=1;i<=n;++i)
    {
        scanf("%d%d",&x,&y);
        g[1].push_back(i+1);
        g[i+1].push_back(1);
        g[n+i+1].push_back(2*n+2);
        g[2*n+2].push_back(n+i+1);
        c[1][i+1]=x;
        c[n+i+1][2*n+2]=y;
        s+=x;
    }
    for (i=1;i<=n;++i)
        for (j=1;j<=n;++j)
            if (i!=j)
            {
                g[i+1].push_back(n+j+1);
                g[n+j+1].push_back(i+1);
                c[i+1][n+j+1]=1;
            }
    n=2*n+2;
    while (bfs())
        for (i=0;i<g[n].size();++i)
        {
            a=g[n][i];
            if ((c[a][n]>f[a][n])&&v[a])
            {
                p[n]=a;
                t=10000;
                for (a=n;a!=1;a=p[a])
                    t=min(t,c[p[a]][a]-f[p[a]][a]);
                for (a=n;a!=1;a=p[a])
                {
                    f[p[a]][a]+=t;
                    f[a][p[a]]-=t;
                }
            }
        }
    printf("%d\n",s);
    for (i=1;i<=n/2;++i)
        for (j=1;j<=n/2;++j)
            if ((j!=i)&&f[i+1][j+n/2])
                printf("%d %d\n",i,j);
    return 0;
}