Cod sursa(job #3190174)

Utilizator tudormiuMiu Tudor Gabriel tudormiu Data 7 ianuarie 2024 03:29:57
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.2 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <climits>
#include <tuple>
#include <queue>
#include <algorithm>

class Node {
public:
    int id;
    std::vector<std::tuple<int, int>> edges;
    explicit Node(int id) : id(id) {}
};

class Edge {
public:
    int start, end;
    int capacity;
    Edge(int s, int e, int c) : start(s), end(e), capacity(c){}
};

class Graph {
public:
    int N, K;
    std::vector<Node> nodes;
    std::vector<Edge> edges;

    explicit Graph(int n, int k = 0) : N(n), K(k) {
        for (int i = 0; i < n; ++i) {
            nodes.emplace_back(i);
        }
    }

    void addNode(int id) {
        nodes.emplace_back(id);
    }

    void addEdge(int start, int end, int capacity) {
        edges.emplace_back(start, end, capacity);

        nodes[start].edges.emplace_back(end, capacity);

        for (auto& edge : nodes[end].edges) {
            if (std::get<0>(edge) == start) {
                return;
            }
        }

        nodes[end].edges.emplace_back(start, 0);  // Add the reverse edge with 0 capacity
    }

    void addDirectedEdge(int start, int end, int capacity) {
        edges.emplace_back(start, end, capacity);
        nodes[start].edges.emplace_back(end, capacity);
    }

    int fordFulkerson(int source, int sink) {
        int maxFlow = 0;

        while (true) {
            // Find augmenting path using BFS
            std::vector<int> parent(N, -1);
            std::queue<std::pair<int, int>> q;  // (node, min_capacity)
            q.push({source, INT_MAX});

            while (!q.empty()) {
                int current = q.front().first;
                int minCapacity = q.front().second;
                q.pop();

                for (const auto& edge : nodes[current].edges) {
                    int neighbor = std::get<0>(edge);
                    int capacity = std::get<1>(edge);

                    if (parent[neighbor] == -1 && capacity > 0) {
                        parent[neighbor] = current;
                        int newMinCapacity = std::min(minCapacity, capacity);

                        if (neighbor == sink) {
                            // Found augmenting path
                            while (neighbor != source) {
                                int prev = parent[neighbor];
                                for (auto& edge : nodes[prev].edges) {
                                    if (std::get<0>(edge) == neighbor) {
                                        std::get<1>(edge) -= newMinCapacity;
                                        break;
                                    }
                                }

                                bool reverseEdgeFound = false;
                                for (auto& edge : nodes[neighbor].edges) {
                                    if (std::get<0>(edge) == prev) {
                                        std::get<1>(edge) += newMinCapacity;
                                        reverseEdgeFound = true;
                                        break;
                                    }
                                }

                                if (!reverseEdgeFound) {
                                    nodes[neighbor].edges.emplace_back(prev, newMinCapacity);
                                }

                                neighbor = prev;
                            }

                            maxFlow += newMinCapacity;
                            break;
                        }

                        q.push({neighbor, newMinCapacity});
                    }
                }
            }

            // No more augmenting paths
            if (parent[sink] == -1) {
                break;
            }
        }

        return maxFlow;
    }

};

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

//    std::istream &in = fin;
//    std::ostream &out = fout;

    std::istream &in = std::cin;
    std::ostream &out = std::cout;

    int n;
    in >> n;

    // Graf g(2 * N + 2);
    //
    //    for (int i = 0; i < N; i++) {
    //        fin >> x >> y;
    //        g.adauga_capacitate(2 * N, i, x);
    //        g.adauga_capacitate(i + N, 2 * N + 1, y);
    //
    //        for (int j = 0; j < N; j++) {
    //            if (i != j)
    //                g.adauga_capacitate(i, j + N, 1);
    //        }
    //    }


    // Create a graph given in the above diagram
    Graph graph(2 * n + 2);

    // Add edges
    std::vector<std::vector<int>> capacity(2 * n + 2, std::vector<int>(2 * n + 2, 0));
    for(int i = 0; i < n; i++)
    {
        int x, y;
        in >> x >> y;
        capacity[2 * n][i] = x;
        capacity[i + n][2 * n + 1] = y;
        for(int j = 0; j < n; j++)
            if(i != j)
                capacity[i][j + n] = 1;
    }

    // Add edges
    for (int i = 0; i < 2 * n + 2; ++i) {
        for (int j = 0; j < 2 * n + 2; ++j) {
            if (capacity[i][j] > 0) {
                graph.addDirectedEdge(i, j, capacity[i][j]);
                graph.addDirectedEdge(j, i, capacity[i][j]);
            }
        }
    }

    // Call the Ford-Fulkerson algorithm
    int source = 0;
    int sink = 2 * n + 1;
    int maxFlow = graph.fordFulkerson(source, sink);

    out << maxFlow << std::endl;
    
    return 0;
}