Cod sursa(job #2422225)

Utilizator preda.andreiPreda Andrei preda.andrei Data 17 mai 2019 22:57:59
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.83 kb
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

using Matrix = vector<vector<int>>;

Matrix MakeMatrix(const vector<pair<int, int>> &degrees)
{
    int nodes = degrees.size();
    Matrix mat(2 * nodes + 2, vector<int>(2 * nodes + 2, 0));

    for (auto i = 1; i <= nodes; i += 1) {
        mat[0][i] = degrees[i - 1].first;
        mat[nodes + i][2 * nodes + 1] = degrees[i - 1].second;
    }
    for (auto i = 1; i <= nodes; i += 1) {
        for (auto j = i + 1; j <= nodes; j += 1) {
            mat[i][nodes + j] = 1;
            mat[j][nodes + i] = 1;
        }
    }
    return mat;
}

bool Bfs(const Matrix &mat, int source, int dest, vector<int> &pred)
{
    pred.assign(mat.size(), -1);

    vector<bool> visited(mat.size(), false);
    queue<int> q;

    visited[source] = true;
    q.push(source);

    while (!q.empty()) {
        auto node = q.front();
        q.pop();

        for (size_t i = 0; i < mat.size(); i += 1) {
            if (mat[node][i] > 0 && !visited[i]) {
                visited[i] = true;
                pred[i] = node;
                q.push(i);
            }
        }
    }
    return visited[dest];
}

int FindMinCapacity(const Matrix &mat, int node, int prev, const vector<int> &pred)
{
    auto res = mat[node][prev];
    while (node != -1) {
        res = min(res, mat[node][prev]);
        prev = node;
        node = pred[node];
    }
    return res;
}

void Flow(Matrix &mat, int node, int prev, const vector<int> &pred)
{
    auto min_capacity = FindMinCapacity(mat, node, prev, pred);
    if (min_capacity <= 0) {
        return;
    }

    while (node != -1) {
        mat[node][prev] -= min_capacity;
        mat[prev][node] += min_capacity;

        prev = node;
        node = pred[node];
    }
}

void FindMaxFlow(Matrix &mat, int source, int dest)
{
    vector<int> pred;
    while (Bfs(mat, source, dest, pred)) {
        for (size_t i = 0; i < mat.size(); i += 1) {
            if (mat[i][dest] > 0) {
                Flow(mat, i, dest, pred);
            }
        }
    }
}

vector<pair<int, int>> Solve(const vector<pair<int, int>> &degrees)
{
    auto mat = MakeMatrix(degrees);
    auto nodes = degrees.size();

    FindMaxFlow(mat, 0, 2 * nodes + 1);

    vector<pair<int, int>> edges;
    for (size_t i = 1; i <= nodes; i += 1) {
        for (size_t j = 1; j <= nodes; j += 1) {
            if (mat[nodes + j][i] > 0) {
                edges.push_back({i, j});
            }
        }
    }
    return edges;
}

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

    int nodes;
    fin >> nodes;

    vector<pair<int, int>> degrees(nodes);
    for (auto &p : degrees) {
        fin >> p.first >> p.second;
    }

    auto res = Solve(degrees);
    fout << res.size() << "\n";

    for (const auto &p : res) {
        fout << p.first << " " << p.second << "\n";
    }

    return 0;
}