Cod sursa(job #1524765)

Utilizator GinguIonutGinguIonut GinguIonut Data 14 noiembrie 2015 13:48:30
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <fstream>
#include <string.h>
#include <limits.h>
#include <vector>
#define nMax 205
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int C[nMax][nMax], F[nMax][nMax], TT[nMax], q[nMax], nod, V, i, a, b, fmin, viz[nMax], S, D, Sum, n, j;
vector<int> G[nMax];
int BF()
{
    memset(viz, 0, sizeof(viz));
    q[0]=viz[S]=1;
    q[1]=S;
    for(int i=1;i<=q[0];i++)
    {
        nod=q[i];
        if(nod==D)
            continue;
        for(int j=0;j<G[nod].size();j++)
        {
            V=G[nod][j];
            if(viz[V] || C[nod][V]==F[nod][V])
                continue;
            q[++q[0]]=V;
            viz[V]=1;
            TT[V]=nod;
        }
    }
    return viz[D];
}
void maxflow()
{
    for(;BF();)
        for(size_t i=0;i<G[D].size();i++)
        {
            nod=G[D][i];
            if(!viz[nod] || C[nod][D]==F[nod][D])
                continue;
            TT[D]=nod;
            fmin=INT_MAX;
            for(nod=D;nod!=S;nod=TT[nod])
                fmin=min(fmin, C[TT[nod]][nod]-F[TT[nod]][nod]);
            if(fmin==0)
                continue;
            for(nod=D;nod!=S;nod=TT[nod])
            {
                F[TT[nod]][nod]+=fmin;
                F[nod][TT[nod]]-=fmin;
            }
        }
}
int main()
{
    fin>>n;
    S=201, D=202;
    for(i=1;i<=n;i++)
    {
        fin>>a>>b;
        Sum+=a+b;
        G[S].push_back(i);
        G[i+100].push_back(S);
        G[i+100].push_back(D);
        G[D].push_back(i+100);
        C[S][i]=a;
        C[i+100][D]=b;
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i!=j)
            {
                C[i][j+100]=1;
                G[i].push_back(j+100);
                G[j+100].push_back(i);
            }
    maxflow();
    fout<<Sum/2<<'\n';
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(F[i][j+100])
                fout<<i<<" "<<j<<'\n';
    return 0;
}