Cod sursa(job #992909)

Utilizator danalex97Dan H Alexandru danalex97 Data 2 septembrie 2013 18:59:15
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 kb
#include <fstream>
#include <cstring>
#include <queue>
using namespace std;

ifstream F("harta.in");
ofstream G("harta.out");

const int Nmax = 210;

int N,M,dad[Nmax],total_in,total_out;
int capacity[Nmax][Nmax];
bool mark[Nmax],in_queue[Nmax];

int BF()
{
    queue<int> Q;
    Q.push( 0 );
    dad[0] = -1;
    in_queue[0] = 1;

    while ( Q.size() )
    {
        int node = Q.front(); Q.pop();
        if ( mark[node] == 1 ) continue;
        mark[node] = 1;

        for (int i=0;i<=M;++i)
            if ( capacity[node][i] > 0 )
                if ( in_queue[i] == 0 )
                {
                    in_queue[i] = 1;
                    dad[i] = node;
                    Q.push(i);
                }
    }

    if ( mark[M] )
        return 1;
    return 0;
}

int main()
{
    F>>N; M=2*N+1;
    for (int i=1,in,out;i<=N;++i)
    {
        F>>in>>out;
        capacity[0][i] = in;
        capacity[N+i][M] = out;
        total_in += in;
        total_out += out;
    }
    for (int i=1;i<=N;++i)
        for (int j=N+1;j<M;++j)
            if ( i != j-N )
                capacity[i][j] = 1;
    while ( BF() )
    {
        for (int i=N+1;i<M;++i)
            if ( capacity[i][M] && mark[i] )
            {
                int actual_flow = capacity[i][M], node = i;
                while ( node != 0 )
                {
                    actual_flow = min(actual_flow,capacity[dad[node]][node]);
                    node = dad[node];
                }
                node = i , capacity[node][M] -= actual_flow;
                while ( node != 0 )
                {
                    capacity[dad[node]][node] -= actual_flow;
                    capacity[node][dad[node]] += actual_flow;
                    node = dad[node];
                }
            }

        memset(dad,0,sizeof(dad));
        memset(mark,0,sizeof(mark));
        memset(in_queue,0,sizeof(in_queue));
    }

    queue<pair<int,int> > edges;
    for (int i=1;i<=N;++i)
        for (int j=N+1;j<M;++j)
            if ( capacity[j][i] > 0 )
                edges.push( make_pair(i,j-N) );
    int nr_edges = edges.size();
    if ( total_in != total_out || total_in != nr_edges )
    {
        G<<"-1\n";
        return 0;
    }
    G<<nr_edges<<'\n';
    while ( edges.size() )
    {
        int x = edges.front().first;
        int y = edges.front().second;
        edges.pop();
        G<<x<<' '<<y<<'\n';
    }
}