Cod sursa(job #1555744)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 23 decembrie 2015 15:11:21
Problema Taramul Nicaieri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.85 kb
/* 
* Metoda:
* Se contureaza reteaua astfel:
* Fiecarui nod i (1 <= i <= N) din graful cautat ii corespund 2 noduri in retea: 
* Nodul 2 * i - 1, nodul de iesire
* Nodul 2 * i, nodul de intrare
* * * * * * * * * * * * * * * *
* Capacitatile vor fi conturate astfel (considerand super-sursa nodul 0, iar super-destinatia nodul 2 * N + 1):
* Arcele super-sursa -> nod iesire vor avea capacitatea         = gradul de iesire al nodului respectiv
* Arcele nod intrare -> super-destinatie vor avea capacitatea   = gradul de intrare al nodului respectiv
* Arcele nod iesire -> nod intrare vor avea capacitatea         = 1
* Problema se reduce la gasirea fluxului maxim.
*/
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_N = 100;
const int NIL = -1;
const int INF = 2e9;

struct Edge
{
    int v, next;
    int cap;
};

Edge G[4 * MAX_N * MAX_N + 4 * MAX_N]; // liste, overkill ..
int head[2 * MAX_N];
int father[2 * MAX_N];                 // vector de tati pentru arborele BFS
int edgePointer[2 * MAX_N];            // pointer catre muchia din arborele BFS
int Q[2 * MAX_N];                      // coada BFS
int qStart, qEnd;
int N;

void addEdge( const int u, const int v, const int cap )
{
    static int buffPtr = 0;

    G[buffPtr].v = v;
    G[buffPtr].cap = cap;
    G[buffPtr].next = head[u];
    head[u] = buffPtr++;
}

int BFS( const int source, const int sink )
{
    const int numVertex = 2 * (N + 1);

    for ( int i = 0; i < numVertex; i++ )
        father[i] = NIL;

    qStart = 0;
    qEnd = 1;
    Q[0] = source;

    while ( qStart != qEnd && father[sink] == NIL )
    {
        int node = Q[qStart++];

        for ( int i = head[node]; i != NIL; i = G[i].next )
        {
            int son = G[i].v;

            if ( father[son] == NIL && G[i].cap )
            {
                father[son] = node;
                edgePointer[son] = i;
                Q[qEnd++] = son;
            }
        }
    }

    int flow = 0;

    for ( int i = head[sink]; i != NIL; i = G[i].next )
    {
        int son = G[i].v;
        if ( father[son] != NIL && G[i ^ 1].cap )
        {
            father[sink] = son;
            edgePointer[sink] = i ^ 1;

            int minFlow = INF;
            int node = sink;

            while ( node != source )
            {
                minFlow = min( minFlow, G[ edgePointer[node] ].cap );
                node = father[node];
            }

            node = sink;

            while ( node != source )
            {
                G[ edgePointer[node] ].cap     -= minFlow;
                G[ edgePointer[node] ^ 1 ].cap += minFlow;
                node = father[node];
            }

            flow += minFlow;
        }
    }
    return flow;
}

int main(void) {
    ifstream in("harta.in");
    ofstream out("harta.out");
    in.tie(0);
    ios_base::sync_with_stdio(0);

    in >> N;

    const int source = 0;
    const int sink = 2 * N + 1;

    for ( int i = source; i <= sink; i++ )
        head[i] = NIL;

    for ( int i = 1; i <= N; ++i ) 
    {
        int inDegree, outDegree;

        in >> inDegree >> outDegree;

        addEdge( source, 2 * i - 1, outDegree );
        addEdge( 2 * i - 1, source, 0 );

        addEdge( 2 * i, sink, inDegree );
        addEdge( sink, 2 * i, 0 );

        for ( int j = 1; j <= N; ++j )
            if ( i != j )
            {
                addEdge( 2 * i - 1, 2 * j, 1 );
                addEdge( 2 * j, 2 * i - 1, 0 );
            }
    }
    in.close();

    int flow = 0, augment;
    do
    {
        augment = BFS( source, sink );
        flow += augment;
    } while ( augment != 0 );

    out << flow << '\n';

    for ( int i = 1; i <= N; i++ )
        for ( int j = head[2 * i - 1]; j != NIL; j = G[j].next )
            if ( G[j].cap == 0 && ( G[j].v / 2 >= && G[j].v / 2 <= N ) )
                out << G[j].v / 2 << ' ' << i << '\n';

    out.close();
    return 0;
}