Cod sursa(job #2955370)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 16 decembrie 2022 20:58:16
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.15 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream fin("harta.in");
ofstream fout("harta.out");

const int NMAX = 100;

int N, inDeg[NMAX + 2], outDeg[NMAX + 2];

int S, D;
vector<int> g[2 * NMAX + 5];
int capacity[2 * NMAX + 5][2 * NMAX + 5], flow[2 * NMAX + 5][2 * NMAX + 5];
int bef[2 * NMAX + 5];

queue<int> Q;
bool seen[2 * NMAX + 5];

bool bfs() {
    for (int i = S; i <= D; i++) { seen[i] = false; }
    Q.push(S);
    seen[S] = true;

    while (!Q.empty()) {
        int node = Q.front();
        Q.pop();

        for (auto it: g[node]) {
            if (!seen[it] && capacity[node][it] > flow[node][it]) {
                seen[it] = true;
                bef[it] = node;
                Q.push(it);
            }
        }
    }
    return seen[D];
}

int main() {
    fin >> N;

    int roads = 0;
    for (int i = 1; i <= N; i++) {
        fin >> outDeg[i] >> inDeg[i];
        roads += outDeg[i];
    }
    fout << roads << '\n';

    S = 0, D = 2 * N + 1;
    for (int i = 1; i <= N; i++) {
        g[S].push_back(i);
        g[i].push_back(S);
        capacity[S][i] = outDeg[i];

        g[i + N].push_back(D);
        g[D].push_back(i + N);
        capacity[i + N][D] = inDeg[i];

        for (int j = 1; j <= N; j++) {
            if (i != j) {
                g[i].push_back(j + N);
                g[j + N].push_back(i);

                capacity[i][j + N] = 1;
            }
        }
    }

    while (bfs()) {
        for (auto it: g[D]) {
            int pumpFlow = capacity[it][D] - flow[it][D];

            for (int node = it; node != S; node = bef[node]) {
                pumpFlow = min(pumpFlow, capacity[bef[node]][node] - flow[bef[node]][node]);
            }

            flow[it][D] += pumpFlow;
            flow[D][it] -= pumpFlow;

            for (int node = it; node != S; node = bef[node]) {
                flow[bef[node]][node] += pumpFlow;
                flow[node][bef[node]] -= pumpFlow;
            }
        }
    }

    for (int i = 1; i <= N; i++) {
        for (auto it: g[i]) {
            if (flow[i][it] == 1) {
                fout << i << ' ' << it - N << '\n';
            }
        }
    }
    return 0;
}