Cod sursa(job #3191644)

Utilizator omaclearuMacelaru Octavian Andrei omaclearu Data 10 ianuarie 2024 11:55:50
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.2 kb
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#include <climits>

using namespace std;

class FlowNetwork {
private:
    static const int Nmax = 301;
    static const int INF = INT_MAX;

    int N;
    int S, D;
    vector<vector<int>> capacity, flow;
    vector<vector<int>> graph;
    vector<int> parent;

public:
    FlowNetwork() : N(0), S(0), D(300) {}

    void readGraph(const string &filename) {
        ifstream inputFile(filename);
        inputFile >> N;

        initializeGraph();

        int a, b;
        for (int i = 1; i <= N; ++i) {
            inputFile >> a >> b;
            addEdge(0, i, a);
            addEdge(i + N, D, b);
            addEdge(D, i + N, 0);
        }

        inputFile.close();

        for (int i = 1; i <= N; ++i)
            for (int j = 1; j <= N; ++j)
                if (i != j && capacity[0][i] && capacity[j + N][D])
                    addEdge(i, j + N, 1);
    }

    void solveMaxFlow() {
        while (bfs()) {
            augmentPath();
        }
    }

    void writeResults(const string &filename) {
        ofstream outputFile(filename);
        vector<pair<int, int>> solution;

        for (int i = 1; i <= N; ++i)
            for (int j = 1; j <= N; ++j)
                if (flow[i][j + N] > 0)
                    solution.emplace_back(i, j);

        outputFile << solution.size() << "\n";
        for (const auto &edge: solution)
            outputFile << edge.first << " " << edge.second << "\n";

        outputFile.close();
    }

private:
    void initializeGraph() {
        capacity.assign(Nmax, vector<int>(Nmax, 0));
        flow.assign(Nmax, vector<int>(Nmax, 0));
        graph.assign(Nmax, vector<int>());
        parent.assign(Nmax, -1);
    }

    void addEdge(int from, int to, int cap) {
        graph[from].push_back(to);
        graph[to].push_back(from);
        capacity[from][to] = cap;
    }

    bool bfs() {
        queue<int> Q;
        bitset<Nmax> visited;

        Q.push(S);
        visited[S] = true;

        while (!Q.empty()) {
            int currentNode = Q.front();
            Q.pop();

            if (currentNode == D)
                continue;

            for (int neighbor: graph[currentNode]) {
                if (!visited[neighbor] && capacity[currentNode][neighbor] > flow[currentNode][neighbor]) {
                    parent[neighbor] = currentNode;
                    visited[neighbor] = true;
                    Q.push(neighbor);
                }
            }
        }

        return visited[D];
    }

    void augmentPath() {
        int minCapacity = INF;
        int current = D;

        while (current != S) {
            int previous = parent[current];
            minCapacity = min(minCapacity, capacity[previous][current] - flow[previous][current]);
            current = previous;
        }

        current = D;
        while (current != S) {
            int previous = parent[current];
            flow[previous][current] += minCapacity;
            flow[current][previous] -= minCapacity;
            current = previous;
        }
    }
};

int main() {
    FlowNetwork flowNetwork;
    flowNetwork.readGraph("harta.in");
    flowNetwork.solveMaxFlow();
    flowNetwork.writeResults("harta.out");

    return 0;
}