Cod sursa(job #1555718)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 23 decembrie 2015 14:52:14
Problema Taramul Nicaieri Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.05 kb
#include <fstream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <iostream>

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[2 * (MAX_N * MAX_N * 2 + 2 * MAX_N)];
int head[MAX_N];
int father[2 * MAX_N];
int edgePointer[2 * MAX_N];
int Q[2 * MAX_N];
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 > 0 )
            {
                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 )
                out << G[j].v / 2 << ' ' << i << '\n';
    
    out.close();
    return 0;
}