Cod sursa(job #2958309)

Utilizator AndreiAncutaAndrei Ancuta AndreiAncuta Data 25 decembrie 2022 21:32:32
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.14 kb
#include <fstream>
#include <limits>
#include <queue>
#include <vector>
#include <iostream>

using std::vector;
using Node = int;

const int INF = std::numeric_limits<int>::max();

class FlowNetwork {
private:
    int nodeCount;
    vector<vector<int>> capacityMatrix;
    vector<vector<int>> flowMatrix;
    vector<vector<Node>> adjList;

    void buildBfsTree(Node s, Node t, vector<Node> &prevInTree) {
        std::fill(prevInTree.begin(), prevInTree.end(), -1);
        prevInTree[s] = -2;

        std::queue<Node> bfsQueue;
        bfsQueue.push(s);

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

            for (Node next: adjList[node]) {
                // Skip visited nodes and saturated edges
                if (prevInTree[next] != -1 || flowMatrix[node][next] == capacityMatrix[node][next])
                    continue;

                if (next == t)
                    continue;

                prevInTree[next] = node;
                bfsQueue.push(next);
            }
        }
    }

    /// Find the minimum capacity through the path from start to end
    int findMinFlowThroughPath(Node start, Node end, vector<Node> &prevInPath) {
        int flow = INF;
        Node current = end;
        while (current != start) {
            Node prevNode = prevInPath[current];
            flow = std::min(flow, capacityMatrix[prevNode][current] - flowMatrix[prevNode][current]);
            current = prevNode;
        }

        return flow;
    }

    /// Update the flows through the path from start to end with the given value
    void updateFlowThroughPath(Node start, Node end, vector<Node> &prevInPath, int flow) {
        Node current = end;
        while (current != start) {
            Node prev = prevInPath[current];
            flowMatrix[prev][current] += flow;
            flowMatrix[current][prev] -= flow;
            current = prev;
        }

    }

    /// Try to find an augmenting path and return the added flow
    int tryAugmentFlow(Node s, Node t, vector<Node> &prevInTree) {
        buildBfsTree(s, t, prevInTree);

        int totalAugmentingFlow = 0;

        // For each node just before t, join it with t and use that as an augmenting path
        for (Node nodeBeforeT: adjList[t]) {
            // Skip node if it was unreachable due to saturation
            if (prevInTree[nodeBeforeT] == -1)
                continue;

            // Join nodeBeforeT and t and update the capacities through the path
            prevInTree[t] = nodeBeforeT;
            auto minFlowThroughPath = findMinFlowThroughPath(s, t, prevInTree);
            updateFlowThroughPath(s, t, prevInTree, minFlowThroughPath);

            totalAugmentingFlow += minFlowThroughPath;
        }

        return totalAugmentingFlow;
    }

public:
    struct Edge {
        Node from;
        Node to;
    };

    explicit FlowNetwork(int nodeCount) : nodeCount(nodeCount) {
        capacityMatrix.resize(nodeCount, vector<int>(nodeCount));
        flowMatrix.resize(nodeCount, vector<int>(nodeCount));
        adjList.resize(nodeCount);
    }

    void addEdge(Node from, Node to, int capacity) {
        adjList[from].push_back(to);
        adjList[to].push_back(from);
        capacityMatrix[from][to] = capacity;
    }

    const vector<Node> &getNeighbors(Node from) {
        return adjList[from];
    }

    int computeMaxFlow(Node s, Node t) {
        int maxFlow = 0;
        vector<Node> prevInPath(nodeCount);

        int newFlow;
        while ((newFlow = tryAugmentFlow(s, t, prevInPath)) > 0) {
            maxFlow += newFlow;
        }

        return maxFlow;
    }

    int getEdgeFlow(Node from, Node to) {
        return flowMatrix[from][to];
    }
};

int main() {
    std::ifstream in("harta.in");

    int townCount;
    in >> townCount;

    int nodeCount = 2 * townCount + 2;
    FlowNetwork network(nodeCount);

    Node s = 0;
    Node t = nodeCount - 1;

    for (Node town = 1; town <= townCount; ++town) {
        int outDegree, inDegree;
        in >> outDegree >> inDegree;

        // Connect s to the town
        network.addEdge(s, town, outDegree);
        // And t to its clone
        Node townClone = town + townCount;
        network.addEdge(townClone, t, inDegree);

        // Connect the town with all other clones
        for (Node otherTown = 1; otherTown <= townCount; ++otherTown) {
            if (town == otherTown) continue;
            Node clone = otherTown + townCount;
            network.addEdge(town, clone, 1);
        }
    }
    in.close();

    network.computeMaxFlow(s, t);

    // The roads are the saturated edges between towns and clones
    vector<FlowNetwork::Edge> edges;
    for (Node town = 1; town <= townCount; ++town) {
        for (Node otherTown = 1; otherTown <= townCount; ++otherTown) {
            if (town == otherTown) continue;
            Node clone = otherTown + townCount;
            if (network.getEdgeFlow(town, clone) == 1) {
                edges.push_back({town, otherTown});
            }
        }
    }

    std::ofstream out("harta.out");
    out << edges.size() << '\n';
    for (auto [from, to] : edges) {
        out << from << ' ' << to << '\n';
    }
    out.close();

    return 0;
}