Cod sursa(job #791974)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 25 septembrie 2012 22:44:45
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 kb
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <cassert>

using namespace std;

const int MaxN = 205;
const int oo = 1000;

vector<int> G[MaxN];
int N, S, D, Cap[MaxN][MaxN], Flow[MaxN][MaxN], Father[MaxN], MaxFlow;
queue<int> Q;

inline void AddEdge(int X, int Y) {
    G[X].push_back(Y), G[Y].push_back(X);
}

inline int In(int X) {
    return X+N;
}

inline int Out(int X) {
    return X;
}

void BuildGraph() {
    for (int X = 1; X <= N; ++X)
        AddEdge(S, Out(X)), AddEdge(In(X), D);
    for (int X = 1; X <= N; ++X)
        for (int Y = 1; Y <= N; ++Y)
            if (X != Y)
                AddEdge(Out(X), In(Y)), Cap[Out(X)][In(Y)] = 1;
}

inline void InitBFS(int Start) {
    memset(Father, -1, sizeof(Father));
    Q.push(Start), Father[Start] = Start;
}

bool BFS(int Start, int End) {
    for (InitBFS(Start); !Q.empty(); Q.pop()) {
        int X = Q.front();
        for (vector<int>::iterator Y = G[X].begin(); Y != G[X].end(); ++Y)
            if (Father[*Y] == -1 && Cap[X][*Y] > Flow[X][*Y])
                Q.push(*Y), Father[*Y] = X;
    }
    return Father[End] != -1;
}

void EdmondsKarp() {
    for (int CFlow; BFS(S, D); MaxFlow += CFlow) {
        CFlow = oo;
        for (int X = D; X != S; X = Father[X])
            CFlow = min(CFlow, Cap[Father[X]][X]-Flow[Father[X]][X]);
        for (int X = D; X != S; X = Father[X])
            Flow[Father[X]][X] += CFlow, Flow[X][Father[X]] -= CFlow;
    }
}

void Solve() {
    BuildGraph();
    EdmondsKarp();
}

void Read() {
    assert(freopen("harta.in", "r", stdin));
    assert(scanf("%d", &N) == 1);
    S = 0, D = 2*N+1;
    for (int X = 1; X <= N; ++X)
        assert(scanf("%d %d", &Cap[S][Out(X)], &Cap[In(X)][D]) == 2);
}

void Print() {
    assert(freopen("harta.out", "w", stdout));
    printf("%d\n", MaxFlow);
    for (int X = 1; X <= N; ++X)
        for (int Y = 1; Y <= N; ++Y)
            if (Flow[Out(X)][In(Y)] > 0)
                printf("%d %d\n", X, Y);
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}