Cod sursa(job #3193746)

Utilizator magistraladoiGagauta Andrei-Paul magistraladoi Data 15 ianuarie 2024 16:31:08
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.46 kb
#include <fstream>
#include <vector>
#include <string>
#include <sstream>
#include <iterator>
#include <tuple>
#include <queue>

std::ifstream in("harta.in");
std::ofstream out("harta.out");

const int inf = 1e9;

class Graf {
private:
    int n, maxim;
    std::vector<std::vector<int>> muchii;
    std::vector<std::vector<int>> capacitati;
    std::vector<int> tata, visited;
    int bfs();
public:
    explicit Graf(int size, int m);
    void adaugaMuchie(std::tuple<int, int, int>);
    std::vector<std::pair<int, int>> flux();
    void setMaxim(int m);
};

Graf::Graf(int size, int m) : n(size), maxim(m), muchii(std::vector<std::vector<int>>(n)), tata(std::vector<int>(size, 0)),
                              visited(std::vector<int>(size, 0)),
                              capacitati(std::vector<std::vector<int>>(n, std::vector<int>(n, 0))) {}

void Graf::adaugaMuchie(std::tuple<int, int, int> x) {
    muchii[std::get<0>(x)].emplace_back(std::get<1>(x));
    capacitati[std::get<0>(x)][std::get<1>(x)] = std::get<2>(x);
}

int Graf::bfs() {
    std::fill(tata.begin(), tata.end(), 0);
    std::fill(visited.begin(), visited.end(), 0);
    std::queue<std::pair<int, int>> q;
    q.emplace(0, inf);
    visited[0] = 1;
    while (!q.empty()) {
        int crt = q.front().first, fluxMin = q.front().second;

        q.pop();
        for (auto &vec : muchii[crt]) {
            if (!visited[vec] && capacitati[crt][vec]) {
                tata[vec] = crt; visited[vec] = 1;
                fluxMin = std::min(fluxMin, capacitati[crt][vec]);
                if (vec == n - 1) {
                    return fluxMin;
                }
                q.emplace(vec, fluxMin);
            }
        }
    }
    return 0;
}

std::vector<std::pair<int, int>> Graf::flux() {
    int capacitateLant, flux = 0;
    while ((capacitateLant = bfs())) {
        flux += capacitateLant;
        int crt = n - 1;
        while (crt != 0) {
            int parent = tata[crt];
            capacitati[parent][crt] -= capacitateLant;
            capacitati[crt][parent] += capacitateLant;
            crt = parent;
        }
    }

    if (flux != maxim) {
        return {};
    }

    int membrii = n / 2 - 1;
    std::vector<std::pair<int, int>> presedinte;
    for (int i = 1; i <= membrii; i++) {
        for (auto &vec : muchii[i]) {
            if (capacitati[i][vec] == 0) {
                presedinte.emplace_back(i, vec - membrii);
            }
        }
    }

    return presedinte;
}

void Graf::setMaxim(int m) {
    maxim = m;
}

int main() {
    int N, maxim = 0;
    in >> N;
    Graf graf(2 * N + 2, 0);
    for (int i = 1; i <= N; i++) {
        int x, y; in >> x >> y; maxim += x;
        graf.adaugaMuchie(std::tuple<int, int, int>{0, i, x});
        graf.adaugaMuchie(std::tuple<int, int, int>{i + N, 2 * N + 1, y});
    }
    graf.setMaxim(maxim);
    for (int i = 1; i <= N; i++) {
        for (int j = N + 1; j <= 2 * N; j++) {
            if (j == i + N) continue;
            graf.adaugaMuchie(std::tuple<int, int, int>{i, j, 1});
            graf.adaugaMuchie(std::tuple<int, int, int>{j, i, 0});
        }
    }

    std::vector<std::pair<int, int>> solutie = graf.flux();
    if (solutie.empty()) {
        out << "0";
    }
    else {
        out << solutie.size() << '\n';
        for (auto &p : solutie) {
            out << p.first << ' ' << p.second << '\n';
        }
    }
    return 0;
}