Cod sursa(job #2615843)

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

using namespace std;

struct Graph {
    vector<vector<int>> cap;
    vector<vector<int>> edges;
    vector<int> pred;

    Graph(int nodes) {
        cap.resize(2 * nodes + 2, vector<int>(2 * nodes + 1, 0));
        edges.resize(2 * nodes + 2);

        for (int i = 1; i <= nodes; i += 1) {
            edges[Source()].push_back(Inner(i));
            edges[Outer(i)].push_back(Dest());

            for (int j = 1; j <= nodes; j += 1) {
                if (i != j) {
                    cap[Inner(i)][Outer(j)] = 1;
                    edges[Inner(i)].push_back(Outer(j));
                    edges[Outer(j)].push_back(Inner(i));
                }
            }
        }
    }

    void SetDegrees(int node, int in, int out) {
        cap[Source()][Inner(node)] = out;
        cap[Outer(node)][Dest()] = in;
    }

    int Source() const {
        return 0;
    }

    int Dest() const {
        return cap.size() - 1;
    }

    int Nodes() const {
        return (cap.size() - 2) / 2;
    }

    int Inner(int node) const {
        return node;
    }

    int Outer(int node) const {
        return node + Nodes();
    }
};

bool FindPath(Graph &graph) {
    graph.pred.assign(graph.cap.size(), -1);
    graph.pred[graph.Source()] = -2;

    queue<int> q;
    q.push(graph.Source());

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

        for (const auto &next : graph.edges[node]) {
            if (graph.pred[next] == -1 && graph.cap[node][next] > 0) {
                graph.pred[next] = node;
                q.push(next);
            }
        }
    }
    return graph.pred[graph.Dest()] != -1;
}

int PathFlow(Graph &graph) {
    int node = graph.Dest();
    int prev = graph.pred[node];
    int flow = graph.cap[prev][node];

    while (prev >= 0) {
        flow = min(flow, graph.cap[prev][node]);
        node = prev;
        prev = graph.pred[node];
    }
    return flow;
}

void FlowPath(Graph &graph) {
    int flow = PathFlow(graph);
    int node = graph.Dest();
    int prev = graph.pred[node];

    while (prev >= 0) {
        graph.cap[prev][node] -= flow;
        graph.cap[node][prev] += flow;
        node = prev;
        prev = graph.pred[node];
    }
}

vector<pair<int, int>> ExtractEdges(Graph &graph) {
    vector<pair<int, int>> edges;
    for (int i = 1; i <= graph.Nodes(); i += 1) {
        for (int j = 1; j <= graph.Nodes(); j += 1) {
            int ni = graph.Inner(i);
            int nj = graph.Outer(j);

            if (graph.cap[nj][ni] > 0) {
                edges.push_back({i, j});
            }
        }
    }
    return edges;
}

vector<pair<int, int>> FindEdges(Graph &graph) {
    while (FindPath(graph)) {
        FlowPath(graph);
    }
    return ExtractEdges(graph);
}

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

    int nodes;
    fin >> nodes;

    Graph graph(nodes);
    for (int i = 1; i <= nodes; i += 1) {
        int out, in;
        fin >> out >> in;
        graph.SetDegrees(i, in, out);
    }

    auto edges = FindEdges(graph);
    fout << edges.size() << "\n";

    for (const auto &e : edges) {
        fout << e.first << " " << e.second << "\n";
    }
    return 0;
}