Cod sursa(job #1444334)

Utilizator ChallengeMurtaza Alexandru Challenge Data 29 mai 2015 16:27:32
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I, Semestrul 2 Marime 2.25 kb
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

const char InFile[]="harta.in";
const char OutFile[]="harta.out";
const int MaxN=256;

ifstream fin(InFile);
ofstream fout(OutFile);

int N,x,y,S,D,T[MaxN],F[MaxN][MaxN],C[MaxN][MaxN],Q[MaxN];
vector<int> A[MaxN];

inline void connect(const int &nod1, const int &nod2, const int &c)
{
    A[nod1].push_back(nod2);
    A[nod2].push_back(nod1);
    C[nod1][nod2]=c;
}

inline int BFS()
{
    int V[MaxN];
    memset(V,0,sizeof(V));
    memset(T,0,sizeof(T));

    Q[0]=0;
    Q[++Q[0]]=S;
    V[S]=1;
    while(Q[0])
    {
        int nod=Q[Q[0]];
        --Q[0];
        for(vector<int>::iterator it=A[nod].begin();it!=A[nod].end();++it)
        {
            if(!V[*it] && C[nod][*it]>F[nod][*it])
            {
                T[*it]=nod;
                V[*it]=1;
                Q[++Q[0]]=*it;
            }
        }
    }
    return T[D];
}

inline int flux()
{
    int flux_maxim=0;
    while(BFS())
    {
        for(vector<int>::iterator it=A[D].begin();it!=A[D].end();++it)
        {
            int nod=*it;
            int minim=C[nod][D]-F[nod][D];
            while(T[nod])
            {
                minim=min(minim,C[T[nod]][nod]-F[T[nod]][nod]);
                nod=T[nod];
            }
            nod=*it;
            F[nod][D]+=minim;
            F[D][nod]-=minim;
            while(T[nod])
            {
                F[T[nod]][nod]+=minim;
                F[nod][T[nod]]-=minim;
                nod=T[nod];
            }
            flux_maxim+=minim;
        }
    }
    return flux_maxim;
}

int main()
{
    fin>>N;
    S=(N<<1)+1;
    D=S+1;
    for(register int i=1;i<=N;++i)
    {
        fin>>x>>y;
        connect(S,i,x);
        connect(i+N,D,y);
    }
    fin.close();

    for(register int i=1;i<=N;++i)
    {
        for(register int j=1;j<=N;++j)
        {
            if(i!=j)
            {
                connect(i,j+N,1);
            }
        }
    }

    fout<<flux()<<"\n";
    for(register int i=1;i<=N;++i)
    {
        for(register int j=1;j<=N;++j)
        {
            if(i!=j)
            {
                if(C[i][j+N]==F[i][j+N])
                {
                    fout<<i<<" "<<j<<"\n";
                }
            }
        }
    }
    fout.close();
    return 0;
}