Cod sursa(job #3190581)

Utilizator mario_deaconescuMario Deaconescu mario_deaconescu Data 7 ianuarie 2024 18:49:10
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 23.41 kb




#include <vector>
#include <cstdio>
#include <queue>
#include <functional>
#include <cmath>
#include <stack>
#include <stdio.h>
#include <optional>
#include <iostream>
#include <limits>

#include <unordered_set>

template<class T = std::nullptr_t, class U = std::nullptr_t, bool directed = false, bool storeParents = true>
class Graph {
public:
    class Node;

    class Edge;

private:
    std::vector<Node *> nodes;
public:
    struct Edge {
        Node *to;
        U data;

        Edge(Node *to) : to(to) {}

        Edge(Node *to, const U &data) : to(to), data(data) {}
    };

    struct EdgePair {
        std::pair<size_t, size_t> pair;
        U data;

        EdgePair(const std::pair<size_t, size_t> &pair) : pair(pair) {}

        EdgePair(const std::pair<size_t, size_t> &pair, const U &data) : pair(pair), data(data) {}

        bool operator==(const EdgePair &other) const {
            return pair == other.pair && data == other.data;
        }

        bool operator!=(const EdgePair &other) const {
            return pair != other.pair || data != other.data;
        }

        bool operator<(const EdgePair &other) const {
            return data < other.data;
        }
    };

    class Node {
    private:
        size_t inDegree = 0;
        size_t outDegree = 0;
        size_t id;
        T data;
        std::vector<Edge> neighbors;
        std::vector<Edge> parents;
    public:
        explicit Node(const size_t &id) : id(id) {}

        Node(const size_t &id, const T &data) : id(id), data(data) {}

        Node(const Node &other) : id(other.id), data(other.data), neighbors(other.neighbors) {}

        Node(Node &&other) noexcept: id(other.id), data(std::move(other.data)), neighbors(std::move(other.neighbors)) {}

        inline bool operator==(const Node &other) const {
            return data == other.data;
        }

        inline bool operator!=(const Node &other) const {
            return data != other.data;
        }

        inline void addNeighbour(Node *neighbor) {
            neighbors.push_back(Edge(neighbor));
            ++neighbor->inDegree;
            outDegree++;
            if (directed) {
                if (storeParents)
                    neighbor->parents.push_back(Edge(this));
            } else {
                neighbor->neighbors.push_back(Edge(this));
                ++neighbor->outDegree;
                inDegree++;
            }
        }

        inline void addNeighbour(Node *neighbor, const U &edgeData) {
            neighbors.push_back(Edge(neighbor, edgeData));
            ++neighbor->inDegree;
            outDegree++;
            if (directed) {
                if (storeParents)
                    neighbor->parents.push_back(Edge(this, edgeData));
            } else {
                neighbor->neighbors.push_back(Edge(this, edgeData));
                ++neighbor->outDegree;
                inDegree++;
            }
        }

        inline std::optional<Edge> getNeighbor(const size_t &neighbourId) const {
            // Find the neighbor with the given id
            for (const Edge &edge: neighbors) {
                if (edge.to->getId() == neighbourId) {
                    return edge;
                }
            }
            return {};
        }

        inline void removeNeighbor(const size_t &neighbourId) {
            // Find the neighbor with the given id
            Graph::Node* neighbor = nullptr;
            if(const auto temp = getNeighbor(neighbourId); temp.has_value()){
                neighbor = temp->to;
            }else {
                return;
            }

            for (size_t i = 0; i < neighbors.size(); i++) {
                if (neighbors[i].to->getId() == neighbourId) {
                    neighbors.erase(neighbors.begin() + i);
                    break;
                }
            }
            --outDegree;
            --neighbor->inDegree;
            if (directed) {
                if (storeParents){
                    // Remove this node from the neighbor's parents
                    for (size_t i = 0; i < neighbor->parents.size(); i++) {
                        if (neighbor->parents[i].to->getId() == id) {
                            neighbor->parents.erase(neighbor->parents.begin() + i);
                            break;
                        }
                    }
                }
            } else {
                for (size_t i = 0; i < neighbor->neighbors.size(); i++) {
                    if (neighbor->neighbors[i].to->getId() == id) {
                        neighbor->neighbors.erase(neighbor->neighbors.begin() + i);
                        break;
                    }
                }
                --neighbor->outDegree;
                --inDegree;
            }
        }

        inline const std::vector<Edge> &getNeighbors() const {
            return neighbors;
        }

        inline const T &getData() const {
            return data;
        }

        inline T &getData() {
            return data;
        }

        inline const size_t &getId() const {
            return id;
        }

        inline const size_t &getInDegree() const {
            return inDegree;
        }

        inline const size_t &getOutDegree() const {
            return outDegree;
        }

        inline const std::vector<Edge> &getParents() const {
            return parents;
        }

        void removeNeighbor(Node *neighbor) {
            for (size_t i = 0; i < neighbors.size(); i++) {
                if (neighbors[i].to == neighbor) {
                    neighbors.erase(neighbors.begin() + i);
                    break;
                }
            }
            neighbor->inDegree--;
            outDegree--;
            if (directed) {
                if (storeParents)
                    for (size_t i = 0; i < neighbor->parents.size(); i++) {
                        if (neighbor->parents[i].to == this) {
                            neighbor->parents.erase(neighbor->parents.begin() + i);
                            break;
                        }
                    }
            } else {
                for (size_t i = 0; i < neighbor->neighbors.size(); i++) {
                    if (neighbor->neighbors[i].to == this) {
                        neighbor->neighbors.erase(neighbor->neighbors.begin() + i);
                        break;
                    }
                }
                neighbor->outDegree--;
                inDegree--;
            }
        }
    };

    Graph() = default;

    Graph(const size_t &totalNodes, const std::vector<EdgePair> &edges, const T &defaultValue) {
        nodes.reserve(totalNodes);
        for (size_t id = 0; id < totalNodes; id++) {
            nodes.push_back(new Node(id, defaultValue));
        }
        for (const auto &edge: edges) {
            const auto &from = edge.pair.first;
            const auto &to = edge.pair.second;
            if (from >= nodes.size()) {
                nodes.resize(from + 1);
            }
            if (to >= nodes.size()) {
                nodes.resize(to + 1);
            }
            nodes[from]->addNeighbour(nodes[to], edge.data);
        }
    }

    Graph(const size_t &totalNodes, const std::vector<EdgePair> &edges) {
        nodes.reserve(totalNodes);
        for (size_t id = 0; id < totalNodes; id++) {
            nodes.push_back(new Node(id));
        }
        for (const auto &edge: edges) {
            const auto &from = edge.pair.first;
            const auto &to = edge.pair.second;
            if (from >= nodes.size()) {
                nodes.resize(from + 1);
            }
            if (to >= nodes.size()) {
                nodes.resize(to + 1);
            }
            nodes[from]->addNeighbour(nodes[to], edge.data);
        }
    }

    Graph(const Graph &other) = delete;

    Graph(Graph &&other) noexcept: nodes(std::move(other.nodes)) {}

    ~Graph() {
        for (auto node: nodes) {
            delete node;
        }
    }

    const size_t size() const {
        return nodes.size();
    }

    typename std::vector<Node *>::iterator begin() {
        return nodes.begin();
    }

    typename std::vector<Node *>::iterator end() {
        return nodes.end();
    }

    typename std::vector<Node *>::const_iterator begin() const {
        return nodes.begin();
    }

    typename std::vector<Node *>::const_iterator end() const {
        return nodes.end();
    }

    inline Node *operator[](const size_t &index) {
        return nodes[index];
    }

    static std::vector<EdgePair> convertEdges(const std::vector<std::vector<int>> &edges) {
        std::vector<EdgePair> result;
        result.reserve(edges.size());
        for (const auto &edge: edges) {
            result.emplace_back(std::make_pair(edge[0], edge[1]));
        }
        return result;
    }

    static std::vector<EdgePair> convertFromNeighborList(const std::vector<std::vector<int>> &neighborList) {
        std::vector<EdgePair> result;
        result.reserve(neighborList.size());
        for (size_t i = 0; i < neighborList.size(); i++) {
            for (const auto &neighbor: neighborList[i]) {
                result.emplace_back(std::make_pair(i, neighbor));
            }
        }
        return result;
    }

    template<class Distance>
    Graph getMinimumSpanningTree_Kruskal(const std::function<double(const U &)> &getWeight, Distance &distance) const {
        distance = 0;
        if (nodes.empty()) {
            return Graph();
        }

        // Create a priority queue to store edges
        auto compare = [&getWeight](const EdgePair &a, const EdgePair &b) {
            return getWeight(a.data) > getWeight(b.data);
        };

        auto totalEdges = getEdges();
        std::priority_queue<EdgePair, std::vector<EdgePair>, decltype(compare)> pq(compare);
        for (const EdgePair &edge: totalEdges) {
            pq.push(edge);
        }
        // Peform Kruskal's algorithm
        std::vector<EdgePair> result;
        result.reserve(nodes.size() - 1);
        size_t components = nodes.size();

        std::vector<size_t> parent(nodes.size());
        for (size_t i = 0; i < nodes.size(); ++i) {
            parent[i] = i;
        }

        const std::function<size_t(const size_t &element)> findParent = [&parent, &findParent](const size_t &element) {
            if (parent[element] == element) {
                return element;
            }
            return parent[element] = findParent(parent[element]);
        };

        const auto merge = [&parent, &findParent, &components](const size_t &from, const size_t &to) {
            const auto fromParent = findParent(from);
            const auto toParent = findParent(to);
            if (fromParent != toParent) {
                parent[fromParent] = toParent;
                --components;
            }
        };

        while (!pq.empty() && components > 1) {
            const EdgePair &edge = pq.top();
            pq.pop();
            size_t from = findParent(edge.pair.first);
            size_t to = findParent(edge.pair.second);
            const auto weight = getWeight(edge.data);
            if (from != to) {
                if (weight == std::numeric_limits<Distance>::max()) {
                    distance = std::numeric_limits<Distance>::max();
                    return {};
                }
                merge(from, to);
                result.push_back(edge);
                distance += weight;
            }
        }

        return {nodes.size(), result};
    }

    template<class Distance>
    Graph getMinimumSpanningTree_Kruskal(const std::function<Distance(const U &)> &getWeight) const {
        Distance distance = 0;
        return getMinimumSpanningTree_Kruskal<Distance>(getWeight, distance);
    }

    template<class Distance>
    Graph getMinimumSpanningTree_Prim(
            const std::function<bool &(Graph::Node *)> &getVisited,
            const std::function<Distance(const U &)> &getWeight,
            Distance &distance) const {
        distance = 0;
        if (nodes.empty()) {
            return Graph();
        }
        // Create a priority queue to store edges
        auto compare = [&getWeight](const Graph::EdgePair &a,
                                    const Graph::EdgePair &b) {
            return getWeight(a.data) > getWeight(b.data);
        };

        std::priority_queue<Graph::EdgePair, std::vector<Graph::EdgePair>, decltype(compare)> pq(
                compare);

        // Start with the first node
        for (const auto &edge: nodes[0]->getNeighbors()) {
            pq.push(Graph::EdgePair(std::make_pair(0, edge.to->getId()), edge.data));
        }

        // Peform Prim's algorithm
        std::vector<Graph::EdgePair> result;
        result.reserve(nodes.size() - 1);

        getVisited(nodes[0]) = true;

        while (!pq.empty() && result.size() < nodes.size() - 1) {
            const Graph::EdgePair edge = pq.top();
            pq.pop();

            if (!getVisited(nodes[edge.pair.second])) {
                getVisited(nodes[edge.pair.second]) = true;
                result.push_back(edge);
                distance += getWeight(edge.data);

                // Add the neighbors of the newly added node to the priority queue
                for (const auto &neighbor: nodes[edge.pair.second]->getNeighbors()) {
                    if (!getVisited(neighbor.to)) {
                        pq.push(Graph::EdgePair(
                                std::make_pair(edge.pair.second, neighbor.to->getId()), neighbor.data));
                    }
                }
            }
        }

        return {nodes.size(), result};
    }

    template<class Distance>
    Graph getMinimumSpanningTree_Prim(
            const std::function<bool &(Graph::Node *)> &getVisited,
            const std::function<Distance(const U &)> &getWeight) const {
        Distance distance = 0;
        return getMinimumSpanningTree_Prim<Distance>(getVisited, getWeight, distance);
    }

    void dfs_from(const size_t &from,
                  const std::function<bool &(Node *)> &getVisited,
                  const std::function<void(Node *)> &nodeCallback,
                  const std::function<void(Node *, Edge)> &edgeCallback) {
        std::stack<Node *> stack;
        stack.push(nodes[from]);
        getVisited(nodes[from]) = true;
        while (!stack.empty()) {
            auto node = stack.top();
            stack.pop();
            nodeCallback(node);
            for (auto neighbor: node->getNeighbors()) {
                if (!getVisited(neighbor.to)) {
                    edgeCallback(node, neighbor);
                    stack.push(neighbor.to);
                    getVisited(neighbor.to) = true;
                }
            }
        }
    }

    void dfs(const std::function<bool &(Node *)> &getVisited,
             const std::function<void(const size_t&, Node *)> &nodeCallback,
             const std::function<void(const size_t&, Node *, Edge)> &edgeCallback) {
        size_t components = 0;
        for (auto root: nodes) {
            if (getVisited(root)) {
                continue;
            }
            dfs_from(root->getId(),
                     getVisited,
                     [=](Graph::Node* node){nodeCallback(components, node);},
                     [=](Graph::Node* node, Graph::Edge edge){edgeCallback(components, node, edge);});
            ++components;
        }
    }

    void bfs_from(const size_t &from,
                  const std::function<bool &(Node *)> &getVisited,
                  const std::function<void(Node*)> &nodeCallback,
                  const std::function<void(Node*, Edge)> &edgeCallback) {
        std::queue<Node *> queue;
        queue.push(nodes[from]);
        getVisited(nodes[from]) = true;
        while (!queue.empty()) {
            auto node = queue.front();
            queue.pop();
            nodeCallback(node);
            for (auto neighbor: node->getNeighbors()) {
                if (!getVisited(neighbor.to)) {
                    edgeCallback(node, neighbor);
                    queue.push(neighbor.to);
                    getVisited(neighbor.to) = true;
                }
            }
        }
    }

    void bfs(const std::function<bool &(Node *)> &getVisited,
             const std::function<void(const size_t&, Node*)> &nodeCallback,
             const std::function<void(const size_t&, Node*, Edge)> &edgeCallback) {
        size_t components = 0;
        for (auto root: nodes) {
            if (getVisited(root)) {
                continue;
            }
            bfs_from(root->getId(),
                     getVisited,
                     [=](Graph::Node* node){nodeCallback(components, node);},
                     [=](Graph::Node* node, Graph::Edge edge){edgeCallback(components, node, edge);});
            ++components;
        }
    }

    std::vector<typename Graph::EdgePair> getEdges() const {
        std::vector<typename Graph::EdgePair> edges;

        for (size_t i = 0; i < nodes.size(); ++i) {
            for (const Edge &edge: nodes[i]->getNeighbors()) {
                edges.push_back(EdgePair(std::make_pair(i, edge.to->getId()), edge.data));
            }
        }

        return edges;
    }

    void DEBUG_PRINT(std::ostream &out = std::cout, bool isOneIndexed = true) const {
        for (const auto &node: nodes) {
            out << node->getId() + isOneIndexed << ": ";
            for (const auto &neighbor: node->getNeighbors()) {
                out << neighbor.to->getId() + isOneIndexed << " ";
            }
            out << std::endl;
        }
    }

    inline const std::vector<Node *> &getNodes() const {
        return nodes;
    }

    template<class Distance>
    std::vector<Distance> minPathDijkstraAll(const size_t &from,
                                             const std::function<Distance(const U &)> &getWeight) const {
        std::vector<Distance> distances(nodes.size(), std::numeric_limits<Distance>::max());
        distances[from] = 0;
        std::priority_queue<std::pair<Distance, Node *>, std::vector<std::pair<Distance, Node *>>, std::greater<>> pq;
        pq.push(std::make_pair(0, nodes[from]));
        while (!pq.empty()) {
            auto [distance, node] = pq.top();
            pq.pop();
            for (const auto &edge: node->getNeighbors()) {
                auto neighbor = edge.to;
                auto newDistance = distance + getWeight(edge.data);
                if (newDistance < distances[neighbor->getId()]) {
                    distances[neighbor->getId()] = newDistance;
                    pq.push(std::make_pair(newDistance, neighbor));
                }
            }
        }
        return distances;
    }

    template<class Distance>
    Distance minPathDijkstra(const size_t &from,
                             const size_t &to,
                             const std::function<Distance(const U &)> &getWeight) const {
        return minPathDijkstraAll(from, getWeight)[to];
    }

    void removeNodeConnections(const size_t& index){
        for(auto node = nodes[index]; auto neighbor : node->getNeighbors()){
            neighbor.to->removeNeighbor(node->getId());
        }
    }

    size_t connectedComponents(const std::function<bool &(Node *)> &getVisited) {
        size_t components = 0;
        bfs(getVisited,
            [&](const size_t& component, Node*){
                components = component + 1;
            },
            [&](const size_t&, Node*, Edge){});
        return components;
    }
};

template<class T = std::nullptr_t, class U = std::nullptr_t, bool storeParents = true>
using DirectedGraph = Graph<T, U, true, storeParents>;

//Taramul Nicaieri
//Harta "Taramului nicaieri" a fost pierduta, dar din fericire se mai stiu cateva date despre ea. Se stie ca exista N orase intre care se afla diferite drumuri. Drumurile "Taramului nicaieri" sunt un pic mai ciudate deoarece daca exista un drum care pleaca din orasul i si ajunge in orasul j nu exista in mod obligatoriu si un drum care pleaca din orasul j si ajunge in orasul i. De asemenea nu vor exista drumuri care pleaca si ajung in acelasi oras. Si nu vor exista mai multe drumuri identice(adica sa coincida si orasul din care pleaca si cel in care se ajunge).Pentru fiecare oras se stie cate drumuri pleaca din el si cate drumuri ajung in el.
//
//Cerinta
//        Scrieti un program care determina drumurile de pe harta initiala.
//
//Date de Intrare
//        Prima linie a fisierului de intrare harta.in contine numarul intreg N, reprezentand numarul de orase. Urmeaza apoi N linii, linia i continand doua numere x,y numarul de drumuri care pleaca din orasul i respectiv numarul de drumuri care intra in orasul i.
//
//Date de Iesire
//        In fisierul harta.out veti afisa pe prima linie numarul M de drumuri construite, apoi vor urma M linii pe fiecare aflandu-se o pereche de numere a,b cu semnificatia exista un drum care pleaca din a si ajunge in b.

#include <fstream>
#include <climits>
#include <deque>

int performBFS(int source,int destination,std::vector<std::vector<int>>& capacity,std::vector<std::vector<int>>& flow,Graph<>& graph,std::vector<int>& parent) {
    std::deque<int> queue;
    std::vector<int> visited(destination+1,0);

    parent.assign(destination+1,0);

    queue.push_back(source);
    visited[source]=1;

    while (!queue.empty()){
        int node=queue.front();
        queue.pop_front();
        if (node==destination)
            break;
        for (auto neighbor:graph[node]->getNeighbors()) {
            int neighborId = neighbor.to->getId();
            if (!visited[neighborId] && capacity[node][neighborId]-flow[node][neighborId]>0) {
                queue.push_back(neighborId);
                parent[neighborId]=node;
                visited[neighborId]=1;
            }
        }
    }
    if (parent[destination]!=0)
        return 1;
    return 0;
}

int performEdmondKarp(int source,int destination,std::vector<std::vector<int>>& capacity,std::vector<std::vector<int>>& flow,Graph<>& graph) {
    int totalFlow=0;
    int minFlow;
    std::vector<int> parent;

    while (performBFS(source,destination,capacity,flow,graph,parent)){
        minFlow=INT_MAX;
        int i=destination;
        while (i!=0) {
            if (capacity[parent[i]][i]-flow[parent[i]][i]<minFlow)
                minFlow=capacity[parent[i]][i]-flow[parent[i]][i];
            i=parent[i];
        }

        i=destination;
        while (i!=0) {
            flow[parent[i]][i]+=minFlow;
            flow[i][parent[i]]-=minFlow;
            i=parent[i];
        }
        totalFlow+=minFlow;
    }
    return totalFlow;
}

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

    int numCities,source,destination;
    source=0;
    fin>>numCities;
    destination=2*numCities+1;

    std::vector<std::vector<int>> capacity(destination+1,std::vector<int>(destination+1,0)),flow(destination+1,std::vector<int>(destination+1,0));
    std::vector<int> parent;

    std::vector<Graph<>::EdgePair> edges;

    for (int i=1;i<=numCities;i++) {
        int outRoads,inRoads;
        fin>>outRoads>>inRoads;
        int cityIndex=numCities+i;

        edges.emplace_back(std::make_pair(source,i));
        edges.emplace_back(std::make_pair(cityIndex,destination));
        capacity[source][i]=outRoads;
        capacity[cityIndex][destination]=inRoads;
    }

    for (int i=1;i<=numCities;i++)
        for (int j=numCities+1;j<=2*numCities;j++)
            if (i!=(j-numCities)){
                edges.emplace_back(std::make_pair(i,j));
                capacity[i][j]=1;
            }

    Graph<> graph(destination+1,edges);
    fout<<performEdmondKarp(source,destination,capacity,flow,graph)<<"\n";

    for (int i=1;i<=numCities;i++)
        for (int j=numCities+1;j<=2*numCities;j++) {
            if (flow[i][j]==1)
                fout<<i<<" "<<j-numCities<<std::endl;
        }
    return 0;
}