Cod sursa(job #3190176)

Utilizator tudormiuMiu Tudor Gabriel tudormiu Data 7 ianuarie 2024 03:42:40
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.71 kb
#include <iostream>
#include <vector>
#include <queue>
#include <cassert>

using namespace std;

#define NX 210

class MaxFlow {
private:
    int S, T, N, flow;
    vector<vector<int>> cap;
    vector<int> pi;
    queue<int> Q;

public:
    MaxFlow() : S(0), T(0), N(0), flow(0) {}

    void readInput() {
        int i, j;

        cin >> N;
        S = 0;
        T = 2 * N + 1;

        cap.resize(NX, vector<int>(NX, 0));
        pi.resize(NX, -1);

        for (i = 1; i <= N; i++) {
            cin >> cap[i + N][T] >> cap[0][i];
        }

        for (i = 1; i <= N; i++) {
            for (j = 1; j <= N; j++) {
                if (i != j) {
                    cap[i][j + N] = 1;
                }
            }
        }

        N = T;
    }

    int minVal(int x, int y) {
        return x < y ? x : y;
    }

    void augment() {
        int i, bot, u, v, z;

        while (true) {
            fill(pi.begin(), pi.end(), -1);
            pi[S] = -2;

            while (!Q.empty()) {
                Q.pop();
            }

            Q.push(S);
            while (!Q.empty() && pi[T] == -1) {
                u = Q.front();
                Q.pop();
                for (i = 0; i <= N; i++) {
                    if (cap[u][i] && pi[i] == -1) {
                        pi[i] = u;
                        Q.push(i);
                    }
                }
            }

            if (pi[T] == -1) {
                break;
            }

            for (z = 0; z <= N; z++) {
                if (cap[z][T] && pi[z] != -1) {
                    bot = cap[z][T];
                    for (u = pi[z], v = z; u >= 0; v = u, u = pi[u]) {
                        bot = minVal(bot, cap[u][v]);
                    }

                    if (bot <= 0) {
                        continue;
                    }

                    cap[z][T] -= bot;
                    cap[T][z] += bot;
                    for (u = pi[z], v = z; u >= 0; v = u, u = pi[u]) {
                        cap[u][v] -= bot;
                        cap[v][u] += bot;
                    }

                    flow += bot;
                }
            }
        }
    }

    void printOutput() {
        int i, j, k = 0;

        cout << flow << endl;
        N >>= 1;

        for (i = 1; i <= N; i++) {
            for (j = 1; j <= N; j++) {
                if (cap[i][j + N] == 0 && i != j) {
                    cout << j << " " << i << endl;
                    k++;
                }
            }
        }

        assert(k == flow);
    }

    void solve() {
        readInput();
        augment();
        printOutput();
    }
};

int main() {
    freopen("harta.in", "r", stdin);
    freopen("harta.out", "w", stdout);

    MaxFlow maxFlow;
    maxFlow.solve();

    return 0;
}