Cod sursa(job #3185196)

Utilizator theo2003Theodor Negrescu theo2003 Data 18 decembrie 2023 12:11:09
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 18.61 kb
// HW for Unibuc AF class

#include <fstream>

#include <vector>
#include <cstdint>
#include <cassert>
#include <queue>
#include <stack>
#include <algorithm>
#include <numeric>

#define uint uint64_t
#define sint int64_t

struct edge {
    uint src;
    uint dst;
    sint cost;
};

struct edge_indexes {
    uint src;
    uint dst;
    uint in_index;
    uint out_index;
};

struct node {
    std::vector<edge> in, out;
};

struct djikstra_result {
    std::vector<uint> distances;
    std::vector<uint> parents;

    std::vector<uint> reconstruct_path(uint node, bool fix_order = true) const {
        assert(node < distances.size());
        std::vector<uint> path;
        while(node != parents[node]) {
            path.push_back(node);
            node = parents[node];
        }
        path.push_back(node);
        if(fix_order) {
            std::reverse(path.begin(), path.end());
        }
        return path;
    }
};

struct union_find {
    std::vector<uint> parent;
    std::vector<uint> size;
    uint find(uint x) {
        assert(x < parent.size());
        uint answer = x;
        while(parent[answer] != answer) {
            answer = parent[answer];
        }
        uint second_pass = x;
        while(parent[second_pass] != second_pass) {
            uint next = parent[second_pass];
            parent[second_pass] = answer;
            second_pass = next;
        }
        return answer;
    }
    void merge(uint a, uint b) {
        assert(a < parent.size());
        assert(b < parent.size());
        a = find(a);
        b = find(b);
        if(a == b) {
            return;
        }
        if(size[a] < size[b]) {
            std::swap(a, b);
        }
        parent[b] = a;
        size[a] += size[b];
    }
};

uint get_mst_cost(const std::vector<edge> &edges) {
    return std::accumulate(edges.begin(), edges.end(), 0, [](const auto &acc, const auto &e) {
        return acc + e.cost;
    });
}

class graph {
    std::vector<node> nodes;
    bool using_union_find = false;
    union_find uf;
public:
    graph() = default;
    uint nr_nodes() {
        return nodes.size();
    }
    void grow(uint size) {
        assert(nodes.size() <= size);
        nodes.resize(size);
    }
    edge_indexes add_edge(uint src, uint dst, sint cost = 1) {
        assert(src < nr_nodes());
        assert(dst < nr_nodes());
        nodes[dst].in.push_back({src, dst, cost});
        nodes[src].out.push_back({src, dst, cost});
        if(using_union_find) {
            uf.merge(src, dst);
        }
        return {src, dst, static_cast<uint32_t>(nodes[dst].in.size() - 1), static_cast<uint32_t>(nodes[src].out.size() - 1)};
    }
    void set_cost(edge_indexes e, sint cost) {
        assert(e.src < nr_nodes());
        assert(e.dst < nr_nodes());
        assert(e.in_index < nodes[e.dst].in.size());
        assert(e.out_index < nodes[e.src].out.size());
        nodes[e.dst].in[e.in_index].cost = cost;
        nodes[e.src].out[e.out_index].cost = cost;
    }
    uint get_cost(edge_indexes e) {
        assert(e.src < nr_nodes());
        assert(e.dst < nr_nodes());
        assert(e.in_index < nodes[e.dst].in.size());
        assert(e.out_index < nodes[e.src].out.size());
        assert(nodes[e.dst].in[e.in_index].cost == nodes[e.src].out[e.out_index].cost);
        return nodes[e.dst].in[e.in_index].cost;
    }

    // Topologically sort the nodes so that any edge A->B means "A comes before B".
    // Any impossible nodes will not appear in the result.
    std::vector<uint> topsort() {
        uint sz = nr_nodes();

        // Remaining dependencies for each node.
        std::vector<uint> remaining(sz);

        // Topsort (found via BFS).
        std::vector<uint> topsort;

        for(uint x = 0; x < sz; x++) {
            remaining[x] = nodes[x].in.size();
            if(remaining[x] == 0) {
                topsort.push_back(x);
            }
        }

        for(uint bfs = 0; bfs < topsort.size(); bfs++) {
            uint node = topsort[bfs];
            for(edge e : nodes[node].out) {
                uint dst = e.dst;
                uint &rem = remaining[dst];
                if(rem != 0) {
                    rem -= 1;
                    if(rem == 0) {
                        topsort.push_back(dst);
                    }
                }
            }
        }

        return topsort;
    }

    // Returns a bipartition if possible, else {false, {}}.
    std::pair<bool, std::vector<bool>> bipartition() {
        enum coloring {
            blank,
            A,
            B
        };
        uint sz = nr_nodes();
        std::vector<coloring> col_vec(sz, blank);
        std::queue<uint> color_from;
        uint colored = 0;
        uint next_node = 0;
        while(true) {
            if(color_from.empty()) {
                // if we finished coloring AND the queue is empty, output the result
                // (if the queue isn't empty, we don't know whether the result is valid yet)
                if(colored == sz) {
                    std::vector<bool> result;
                    result.resize(sz);
                    for(uint x = 0;x < sz;x++) {
                        assert(col_vec[x] != blank);
                        result[x] = (col_vec[x] == A);
                    }
                    return {true, result};
                }

                // if the queue is empty BUT we haven't finished coloring, then
                // we must have finished col_vec one connected component
                // pick a new node to continue the BFS in a new component
                while(col_vec[next_node] != blank) {
                    next_node++;
                    assert(next_node != sz);
                }
                // so that this works with undirected graphs, check neighbors of next_node since it may be connected
                // to a colored node
                col_vec[next_node] = A;
                for(auto e : nodes[next_node].out) {
                    if(col_vec[e.dst] == A) {
                        col_vec[e.dst] = B;
                        break;
                    }
                }
                colored++;
                color_from.push(next_node);
            }
            uint node = color_from.front();
            assert(col_vec[node] != blank);
            color_from.pop();
            for(auto e : nodes[node].out) {
                if(col_vec[e.dst] == blank) {
                    col_vec[e.dst] = (col_vec[node] == A ? B : A);
                    colored++;
                    color_from.push(e.dst);
                } else if(col_vec[e.dst] == col_vec[node]) {
                    // adjacent equal colors not allowed
                    return {false, {}};
                }
            }
        }
    }

    struct bfs_result {
        uint node;
        uint distance;
    };

    std::vector<bfs_result> bfs_distances(const std::vector<uint> &sources) {
        uint sz = nr_nodes();
        std::vector<bfs_result> bfs;
        std::vector<char> visited(sz, false);
        for(uint x : sources) {
            assert(x < sz);
            bfs.push_back({x, 0});
            visited[x] = true;
        }
        for(uint x = 0;x < bfs.size();x++) {
            for(auto e : nodes[bfs[x].node].out) {
                if(!visited[e.dst]) {
                    visited[e.dst] = true;
                    bfs.push_back({e.dst, bfs[x].distance + 1});
                }
            }
        }
        return bfs;
    }

    std::vector<uint> components() {
        uint sz = nr_nodes();
        std::vector<uint> comp(sz, UINT64_MAX);
        uint next_comp = 0;
        for(uint x = 0;x < sz;x++) {
            if(comp[x] == UINT64_MAX) {
                auto bfs_result = bfs_distances({x});
                for(auto r : bfs_result) {
                    comp[r.node] = next_comp;
                }
            }
            next_comp++;
        }
        for(uint x = 0;x < sz;x++) {
            assert(comp[x] != UINT64_MAX);
        }
        return comp;
    }

    struct node_w_dfs_result {
        uint open; // time we discovered this node
        uint close; // node with lowest open time that we can reach from this node
    };

    // DFS to find open and close times for each node, UINT64_MAX if unreachable, single source
    std::vector<node_w_dfs_result> dfs_open_close(uint root) {
        uint sz = nr_nodes();
        assert(root < sz);

        std::vector<node_w_dfs_result> result(sz, {UINT64_MAX, UINT64_MAX});
        const auto open = [&](uint x) -> uint& {
            return result[x].open;
        };
        const auto close = [&](uint x) -> uint& {
            return result[x].close;
        };

        struct stack_frame {
            uint node;
            uint parent;
            uint next_child;
        };
        // allocate the stack on the heap to avoid stack overflow
        std::stack<stack_frame> call_stack;
        uint next_open = 0;

        const auto call = [&](uint node, uint parent) {
            assert(open(node) == UINT64_MAX);
            assert(close(node) == UINT64_MAX);
            open(node) = close(node) = next_open++;
            call_stack.push({node, parent, 0});
        };

        call(root, UINT64_MAX);

        while(!call_stack.empty()) {
            uint node = call_stack.top().node;
            uint child_index = call_stack.top().next_child;
            assert(child_index <= nodes[node].out.size());

            if(child_index == nodes[node].out.size()) {
                // end of this call
                call_stack.pop();
                if(!call_stack.empty()) {
                    // update parent's close time
                    uint parent = call_stack.top().node;
                    close(parent) = std::min(close(parent), close(node));
                }
                continue; // return from this call
            }

            uint child = nodes[node].out[child_index].dst;
            call_stack.top().next_child++; // update index for next iteration

            if(child == call_stack.top().parent) {
                continue; // continue to next iteration
            } else if(open(child) == UINT64_MAX) {
                call(child, node);
                continue; // recurse
            } else {
                close(node) = std::min(close(node), open(child));
                continue; // continue to next iteration
            }
        }

        return result;
    }

    djikstra_result dijkstra(uint root) {
        uint sz = nr_nodes();
        assert(root < sz);

        std::vector<uint> distances(sz, UINT64_MAX);
        std::vector<uint> parents(sz, UINT64_MAX);
        std::vector<bool> visited(sz, false);

        struct lazy_dji_node {
            uint node;
            uint distance;

            bool operator<(const lazy_dji_node &other) const {
                // priority queue is a max heap, so we want to return true if this distance is smaller
                return distance > other.distance;
            }
        };

        std::priority_queue<lazy_dji_node> pq;
        distances[root] = 0;
        parents[root] = root;
        pq.push({root, 0});

        while(!pq.empty()) {
            auto top = pq.top();
            // once a node is visited never look at it again (assume no negative edges)
            visited[top.node] = true;
            pq.pop();
            if(top.distance != distances[top.node]) {
                // we've already found a shorter path to this node
                // lazy djikstra does not use a decrease-key operation, so ignore instead
                continue;
            }
            for(auto e : nodes[top.node].out) {
                assert(e.cost >= 0);
                uint relaxed_distance = top.distance + e.cost;
                if(relaxed_distance < distances[e.dst]) {
                    distances[e.dst] = relaxed_distance;
                    parents[e.dst] = top.node;
                    pq.push({e.dst, relaxed_distance});
                }
            }
        }
        return {distances, parents};
    }

    void init_union_find() {
        uint sz = nr_nodes();
        uf.size = std::vector<uint>(sz, 1);
        uf.parent.resize(sz);
        for(uint x = 0;x < sz;x++) {
            uf.parent[x] = x;
        }
        using_union_find = true;
    }

    uint find(uint x) {
        assert(x < nr_nodes());
        assert(using_union_find);
        return uf.find(x);
    }

    uint find_size(uint x) {
        assert(x < nr_nodes());
        assert(using_union_find);
        return uf.size[uf.find(x)];
    }

    std::vector<edge> mst() {
        union_find mst_uf{std::vector<uint>(nr_nodes()), std::vector<uint>(nr_nodes(), 1)};
        for(uint x = 0;x < nr_nodes();x++) {
            mst_uf.parent[x] = x;
        }
        std::vector<edge> edges;
        for(uint x = 0;x < nr_nodes();x++) {
            edges.insert(edges.end(), nodes[x].out.begin(), nodes[x].out.end());
        }
        std::sort(edges.begin(), edges.end(), [](const edge &a, const edge &b) {
            return a.cost < b.cost;
        });
        std::vector<edge> mst;
        for(const auto &e : edges) {
            if(mst_uf.find(e.src) != mst_uf.find(e.dst)) {
                mst_uf.merge(e.src, e.dst);
                mst.push_back(e);
            }
        }
        return mst;
    }

    struct flow_edge {
        uint src;
        uint dst;
        sint flow;
        sint capacity;
    };

    struct flow_result {
        uint total;
        std::vector<std::vector<flow_edge>> edges;
    };

    flow_result edmonds_karp(uint src, uint dst) {
        flow_result flow{0, {}};

        std::vector<std::vector<flow_edge*>> back_edges;

        flow.edges.resize(nodes.size());
        back_edges.resize(nodes.size());
        for(uint x = 0;x<nodes.size();x++) {
            flow.edges[x].resize(nodes[x].out.size());
            for(uint y = 0;y<nodes[x].out.size();y++) {
                auto &edge = nodes[x].out[y];
                flow.edges[x][y] = flow_edge{edge.src, edge.dst, 0, edge.cost};
                back_edges[edge.dst].push_back(&flow.edges[x][y]);
            }
        }

        struct flow_bfs_step {
            uint node;
            uint prev_step;
            flow_edge *via;
            bool is_back_edge;
        };

        std::vector<flow_bfs_step> bfs;
        std::vector<char> visited(flow.edges.size());

        // loop until BFS fails
        for(;;) {
            // try to find a path
            bfs.clear();
            std::fill(visited.begin(), visited.end(), false);
            bfs.push_back({src, 0, nullptr, false});
            for(uint i = 0;i<bfs.size();i++) {
                uint node = bfs[i].node;
                // check forward edges
                auto &out_edges = flow.edges[node];
                for(flow_edge &edge : out_edges) {
                    if(edge.flow == edge.capacity || visited[edge.dst]) {
                        continue;
                    }
                    visited[edge.dst] = true;
                    bfs.push_back({edge.dst, i, &edge, false});
                    // check if we found a path
                    if(bfs.back().node == dst) {
                        goto break_outer__path_found;
                    }
                }
                // check backward edges
                const auto &in_edges = back_edges[node];
                for(uint j = 0;j<in_edges.size();j++) {
                    flow_edge &edge = *in_edges[j];
                    if(edge.flow == 0 || visited[edge.src]) {
                        continue;
                    }
                    visited[edge.src] = true;
                    bfs.push_back({edge.src, i, &edge, true});
                    // check if we found a path
                    if(bfs.back().node == dst) {
                        goto break_outer__path_found;
                    }
                }
            }
            break;
            break_outer__path_found:
            // trace path, perform updates
            sint flow_increase = INT64_MAX;
            for(uint last_step = bfs.size() - 1;last_step != 0;last_step = bfs[last_step].prev_step) {
                const auto &edge = *bfs[last_step].via;
                if(bfs[last_step].is_back_edge) {
                    flow_increase = std::min(flow_increase, edge.flow);
                } else {
                    flow_increase = std::min(flow_increase, edge.capacity - edge.flow);
                }
            }
            assert(flow_increase > 0);
            for(uint last_step = bfs.size() - 1;last_step != 0;last_step = bfs[last_step].prev_step) {
                auto &edge = *bfs[last_step].via;
                if(bfs[last_step].is_back_edge) {
                    assert(flow_increase <= edge.flow);
                    edge.flow -= flow_increase;
                } else {
                    assert(flow_increase <= (edge.capacity - edge.flow));
                    edge.flow += flow_increase;
                }
            }
        }

        // calculate total flow
        for(const auto &edge : flow.edges[src]) {
            flow.total += edge.flow;
        }

        return flow;
    }
};

const int MAX_NODES = 100;
const int FLOW_SOURCE = MAX_NODES * 2;
const int FLOW_SINK = MAX_NODES * 2 + 1;
/*
 * 0 -> 99 | start of a path
 * 100 -> 199 | end of a path
 * 200 | flow source
 * 201 | flow sink
 */

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

int main() {

    graph g;
    g.grow(MAX_NODES * 2 + 2);

    for(uint x = 0;x < MAX_NODES;x++) {
        for(uint y = 0;y < MAX_NODES;y++) {
            if(x != y) {
                g.add_edge(x, y + MAX_NODES, 1);
            }
        }
    }

    uint n;
    in >> n;
    uint expected_flow = 0;
    for(uint x = 0, in_degree, out_degree;x < n;x++) {
        in >> in_degree >> out_degree;
        expected_flow += in_degree;
        g.add_edge(FLOW_SOURCE, x, in_degree);
        g.add_edge(x + MAX_NODES, FLOW_SINK, out_degree);
    }

    const auto flow = g.edmonds_karp(MAX_NODES * 2, MAX_NODES * 2 + 1);

    assert(flow.total == expected_flow);

    out << flow.total << '\n';

    for(const auto &node : flow.edges) {
        for(const auto &edge : node) {
            if(edge.flow != 0 && edge.src != FLOW_SOURCE && edge.dst != FLOW_SINK) {
                assert(edge.flow > 0);
                out << edge.src + 1 << ' ' << edge.dst - MAX_NODES + 1 << '\n';
            }
        }
    }

}