Cod sursa(job #1160524)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 30 martie 2014 16:46:54
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int Nmax = 202;
const int inf = 1e9;

vector <int> G[Nmax];
int C[Nmax][Nmax];
int F[Nmax][Nmax];
int tata[Nmax], vis[Nmax], coada[Nmax];

int N;

inline bool BFS( int S, int D )
{
    for ( int i = 0; i <= D; ++i )
            vis[i] = 0;

    int st = 1, dr = 1;
    coada[1] = S;
    vis[S] = 1;
    tata[S] = 0;

    while ( st <= dr )
    {
        int nod = coada[ st++ ];

        for ( auto vecin: G[nod] )
        {
            if ( !vis[vecin] && C[nod][vecin] > F[nod][vecin] )
            {
                vis[vecin] = 1;
                tata[vecin] = nod;
                coada[ ++dr ] = vecin;

                if ( vecin == D )
                        return true;
            }
        }
    }

    return false;
}

int EdmondsKarp( int S, int D )
{
    int flow = 0, fmin;

    while ( BFS( S, D ) )
    {
        for ( auto vecin: G[D] )
        {
            if ( !vis[vecin] || F[vecin][D] >= C[vecin][D] ) continue;

            tata[D] = vecin;
            fmin = inf;

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

            if ( fmin == 0 ) continue;

            for ( int nod = D; nod != S; nod = tata[nod] )
            {
                F[ tata[nod] ][nod] += fmin;
                F[nod][ tata[nod] ] -= fmin;
            }

            flow += fmin;
        }
    }

    return flow;
}

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

    f >> N;

    int S = 0, D = 2 * N + 1;

    for ( int i = 1, a, b; i <= N; ++i )
    {
        f >> a >> b;

        G[S].push_back( i );
        G[i].push_back( S );
        C[S][i] = a;

        G[i + N].push_back( D );
        G[D].push_back( i + N );
        C[i + N][D] = b;
    }

    for ( int i = 1; i <= N; ++i )
            for ( int j = 1; j <= N; ++j )
                if ( i != j )
                {
                    G[i].push_back( j + N );
                    G[j + N].push_back( i );
                    C[i][j + N] = 1;
                }

    g << EdmondsKarp( S, D ) << "\n";

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

    return 0;
}