Cod sursa(job #1051865)

Utilizator narcis_vsGemene Narcis - Gabriel narcis_vs Data 10 decembrie 2013 17:23:15
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.27 kb
#include <fstream>
#include <bitset>
#include <queue>

using namespace std;
const int NMax = 204;
int C[NMax][NMax];
int F[NMax][NMax];
bitset < NMax > viz;
int degreein[NMax],degreeout[NMax];
int n,source, destination , Father[NMax];
inline void Read()
{
    ifstream f("harta.in");
    f >> n ;
    for(int i = 1 ;i <= n; ++i)
        f >> degreeout[i] >> degreein[i] ;
    f.close();
}

inline void BuildGraph()
{
    int i ,j ;
    source = 0;
    destination = 2*n+1;
    for(i = 1;i <= n; ++i)
    {
        C[source][i] = degreeout[i];
        C[i+n][destination] = degreein[i];
        for(j = n+1;j < destination; ++j)
            if(i != j-n)
                C[i][j] = 1;
    }
}

inline bool BFS()
{
    viz = 0;
    queue < int >Q;
    int node, i;
    viz[source] = 1;
    for(Q.push(source); !Q.empty(); Q.pop())
    {
        node = Q.front();

        if(node==destination)
            continue;
        for(i = 1;i <= destination; ++i)
            if(!viz[i] && F[node][i] < C[node][i])
            {
                viz[i]  = 1;
                Q.push(i);
                Father[i] = node;
            }
    }
    return viz[destination];
}

inline void MaxFlow()
{
    int i,node;
    while(BFS())
    {
        for(i = n+1;i < destination;  ++i)
        {
            if(!viz[i] || !C[i][destination] || F[i][destination] == C[i][destination])
                continue;
            Father[destination] = i;
            int minn = NMax;
            for(node = destination ; node != source ;node= Father[node])
                minn = min(C[Father[node]][node]-F[Father[node]][node],minn);
            if(!minn)
                continue;
            for(node = destination ; node != source ;node = Father[node])
            {
                F[Father[node]][node]++;
                F[node][Father[node]]--;
            }
        }
    }
}

inline void Write()
{
    vector < pair < int , int >  > sol;
    int i,j;
    for(i = 1;i <= n;++i)
        for(j = n+1;j < destination; ++j)
            if(F[i][j] ==1)
                sol.push_back(make_pair(i,j-n));
    ofstream g("harta.out");
    g<< ( j =  sol.size())<<"\n";
    for(i = 0 ; i < j ; ++i)
        g<<sol[i].first<<" "<<sol[i].second<<"\n";
    g.close();
}

int main()
{
    Read();
    BuildGraph();
    MaxFlow();
    Write();
    return 0;
}