Cod sursa(job #1162436)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 31 martie 2014 20:16:55
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <iostream>
#include <fstream>
#include <bitset>
#include <vector>

#define per pair<int,int>
#define DN 205
#define x first
#define y second
#define pb push_back
#define INF (1<<30)
using namespace std;

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

int n,S,D,C[DN][DN],F[DN][DN],t[DN],arb[DN],flow;
vector < int > list[DN];
bitset < DN > viz;

void read(){

    f>>n;
    S = 0; D = n + n + 1;

    for(int i=1;i<=n;++i){

        int a,b;
        f>>a>>b;
        C[S][i] = a;
        C[n + i][D] = b;
        list[S].pb(i);
        list[i].pb(S);
        list[n + i].pb(D);
        list[D].pb(n + i);
    }
}
void build_graph(){

    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            if(i!=j){

                list[i].pb(n+j);
                list[n +j].pb(i);
                C[i][n + j] = 1;
            }
}

bool bf(){

    viz&=0;
    arb[0] = 1;
    arb[1] = S;
    viz[S] = 1;
    for(int i=1;i<=arb[0];++i){

        int nod = arb[i];
        if( nod == D )
            continue;

        for(int j=0;j<list[nod].size();++j){

            int next_nod = list[nod][j];
            if( C[nod][next_nod] == F[nod][next_nod] || viz[next_nod]) continue;
            viz[next_nod] = 1;
            arb[ ++arb[0]] = next_nod;
            t[next_nod] = nod;
        }
    }
    return viz[D];
}

void solve(){

    bool exista_flux = true;
    for(;exista_flux;){

        exista_flux = bf();

        for(int i=n + 1;i<=n + n;++i){ /// iau vecinii destinatiei

            int nod = i, fmin = INF;
            if(C[nod][D] == F[nod][D] || !viz[nod])
                continue;
            t[ D ] = nod;

            for( nod = D ; nod!=S ; nod = t[nod])
                fmin=min(fmin,C[ t[nod] ][ nod ] - F[ t[nod] ][ nod ] );

            if(fmin == 0)
                continue;

            for( nod = D; nod!=S ; nod = t[nod]){

                F[ t[nod] ][ nod ] += fmin;
                F[ nod ][ t[nod] ] -= fmin;
            }
            flow+=fmin;
        }
    }

}

void write(){

    g<<flow<<"\n";
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            if(F[i][n + j])
                g<<i<<" "<<j<<endl;
}

int main()
{
    read();
    build_graph();
    solve();
    write();
    return 0;
}