Cod sursa(job #1212662)

Utilizator acomAndrei Comaneci acom Data 25 iulie 2014 15:16:31
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include<cstdio>
#include<vector>
#include<bitset>
#include<queue>
using namespace std;
vector <int> v[105];
queue <int> q;
bitset <210> viz;
int n,m,p,x,y,T[210],C[210][210],F[210][210];
int bfs()
{
    int i;
    viz.reset();
    for (i=0;i<=2*n+1;++i)
        T[i]=-1;
    viz[0]=1; q.push(0);
    while (!q.empty())
    {
        x=q.front(); q.pop();
        for (i=0;i<v[x].size();++i)
        {
            y=v[x][i];
            if (!viz[y] && C[x][y]>F[x][y])
            {
                viz[y]=1, T[y]=x;
                q.push(y);
            }
        }
    }
    return viz[2*n+1];
}
int main()
{
    int i,j;
    freopen("harta.in","r",stdin);
    freopen("harta.out","w",stdout);
    scanf("%d",&n);
    for (i=1;i<=n;++i)
    {
        scanf("%d%d",&x,&y);
        v[0].push_back(i); v[i].push_back(0);
        v[i+n].push_back(2*n+1); v[2*n+1].push_back(i+n);
        C[0][i]=x;
        C[i+n][2*n+1]=y;
    }
    for (i=1;i<=n;++i)
        for (j=1;j<=n;++j)
            if (i!=j)
            {
                v[i].push_back(j+n), v[j+n].push_back(i);
                C[i][j+n]=1;
            }
    while (bfs())
        for (i=0;i<v[2*n+1].size();++i)
        {
            x=v[2*n+1][i];
            if (viz[x] && C[x][2*n+1]>F[x][2*n+1])
            {
                p=C[x][2*n+1]-F[x][2*n+1];
                while (!(T[x]<0))
                {
                    p=min(p,C[T[x]][x]-F[T[x]][x]);
                    x=T[x];
                }
                m+=p;
                x=v[2*n+1][i];
                F[x][2*n+1]+=p, F[2*n+1][x]-=p;
                while (!(T[x]<0))
                {
                    F[T[x]][x]+=p, F[x][T[x]]-=p;
                    x=T[x];
                }
            }
        }
    printf("%d\n",m);
    for (i=1;i<=n;++i)
        for (j=1;j<=n;++j)
            if (F[i][j+n]==1)
                printf("%d %d\n",i,j);
    return 0;
}