Cod sursa(job #333135)

Utilizator cezarbotolanbotolan cezar cezarbotolan Data 21 iulie 2009 16:09:17
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 kb
#include<fstream>
#include<vector>
#include<queue>
#include<cstring>

using namespace std;

ifstream f("harta.in");
ofstream g("harta.out");

const int maxn=220;
const int INF=0x3f3f3f3f;

queue<int>Q;
vector<int>a[maxn];

int F[maxn][maxn],C[maxn][maxn],i,j,n,m,x,gradei[maxn],gradeo[maxn];

int val[maxn],source,dest;

int bfs()
{
    int x;
    memset(val,0,sizeof(val));
    Q.push(source);
    val[source]=INF;
    while(!Q.empty())
    {
        x=Q.front();
        Q.pop();
        if(x==dest)
            continue;
        for(vector<int>::iterator it=a[x].begin();it!=a[x].end();++it)
            if(val[*it]==0&&F[x][*it]!=C[x][*it])
                val[*it]=x,Q.push(*it);
    }

    return val[dest];
}

int main()
{
    f>>n;
    source=2*n+2;;
    dest=2*n+1;
    for(i=1;i<=n;++i)
    {
        f>>gradei[i];
        f>>gradeo[i];
        a[source].push_back(i);
        a[i].push_back(source);
        C[source][i]=gradei[i];
        a[i+n].push_back(dest);
        a[dest].push_back(i+n);
        C[i+n][dest]=gradeo[i];
    }

    for(i=1;i<=n;++i)
        for(j=i+1;j<=n;++j)
        {
            a[i].push_back(j+n);
            a[j+n].push_back(i);
            C[i][j+n]=1;
            a[j].push_back(i+n);
            a[i+n].push_back(j);
            C[j][i+n]=1;
        }

    int flow,fmin;
    for(flow=0;bfs();)
        for(vector<int>::iterator it=a[dest].begin();it!=a[dest].end();++it)
        {
            x=*it;
            if(val[x]==0||F[x][dest]==C[x][dest])
                continue;
            fmin=INF;
            val[dest]=x;
            for(i=dest;i!=source;i=val[i])
                fmin=min(fmin,C[val[i]][i]-F[val[i]][i]);

            if(fmin==0)
                continue;
            for(i=dest;i!=source;i=val[i])
                F[val[i]][i]+=fmin,F[i][val[i]]-=fmin;
            flow+=fmin;
        }

    g<<flow<<"\n";
    for(i=1;i<=n;++i)
        for(j=n+1;j<=n*2;++j)
            if(F[i][j]==1)
                g<<i<<" "<<j-n<<"\n";

    f.close();
    g.close();

    return 0;
}