Cod sursa(job #992913)

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

/**

Putem modela problema cu ajutorul unei retele de flux.

O sa construim un graf bipartit cu cele N noduri in ablele parti si vom adauga
o sursa si o destinatie. Costurile vor fi urmatoarele:

- muchie in graf bipartit - cost 1
- muchie de la sursa la stanga - cost de intrare
- muchie de la dreapta la destinatie - cost de iesire

Avem garantia ca fluxul maxim va alege muchiile astefel incat sa gradele de intrare
si iesire vor fi respectate. Nu este solutie cand suma gradelor de intrare si iesire
sunt diferite sau cand aceasta suma nu e egala cu fluxul maxim gasit.

*/

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';
    }
}