Cod sursa(job #3188034)

Utilizator LazarDanielGabrielLazar Daniel-Gabriel LazarDanielGabriel Data 1 ianuarie 2024 13:00:10
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.36 kb
#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
#include <fstream>

using namespace std;

ifstream f("harta.in");
ofstream g("harta.out");

// Structura pentru reprezentarea unei muchii
struct Edge {
    int destination;  // nodul destinatar
    int capacity;     // capacitatea maximă a muchiei
    int flow;         // fluxul curent pe muchie
    int residual;     // capacitatea reziduală a muchiei

    Edge(int v, int c) {
        destination = v;
        capacity = c;
        flow = 0;
        residual = capacity;
    }
};

class Graph {
    int V;                 // numărul de noduri
    vector<vector<Edge>> adj;  // listă de adiacență pentru reprezentarea grafului

public:
    Graph(const int& V) : V(V), adj(V + 2) {}

    // Adaugă o muchie în graf
    void AddEdge(const int& u, const int& v, const int& c) {
        Edge e_u(v, c);
        Edge e_v(u, 0);
        adj[u].push_back(e_u);
        adj[v].push_back(e_v);
    }

    // Algoritmul lui Edmonds-Karp pentru calcularea fluxului maxim într-o rețea
    int EdmondsKarp(int source, int sink) {
        int maxFlow = 0;

        while (true) {
            vector<int> parent(V + 2, -1);
            queue<pair<int, int>> q;
            q.push({source, INT_MAX});

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

                for (const Edge& e : adj[u]) {
                    int v = e.destination;
                    if (parent[v] == -1 && e.residual > 0) {
                        parent[v] = u;

                        // Actualizăm capacitatea minimă pe drum
                        int newMinCapacity = min(minCapacity, e.residual);
                        q.push({v, newMinCapacity});

                        if (v == sink) {
                            int pathFlow = newMinCapacity;
                            int current = v;

                            while (current != source) {
                                int previous = parent[current];
                                for (Edge& edge : adj[previous]) {
                                    if (edge.destination == current) {
                                        edge.residual -= pathFlow;
                                        edge.flow += pathFlow;
                                        break;
                                    }
                                }

                                for (Edge& reverseEdge : adj[current]) {
                                    if (reverseEdge.destination == previous) {
                                        reverseEdge.residual += pathFlow;
                                        break;
                                    }
                                }
                                current = previous;
                            }

                            maxFlow += pathFlow;
                            break;
                        }
                    }
                }
            }

            if (parent[sink] == -1) {
                break;
            }
        }

        return maxFlow;
    }

    // Afișează detaliile muchiilor (pentru debugare)
    void Afisare() {
        for (int i = 0; i <= V + 1; i++)
            for (auto e : adj[i])
                cout << i << " " << e.destination << " " << e.capacity << " " << e.flow << " " << e.residual << "\n";
    }

    // Afișează drumurile rezultate (muchii cu capacitatea maximă)
    void Roads() {
        for (int i = 1; i <= V / 2; i++) {
            for (auto e : adj[i]) {
                if (e.residual == 0 && e.capacity)
                    g << i << " " << e.destination - V / 2 << endl;
            }
        }
    }
};

int main() {
    int N;
    f >> N;
    int source = 0;
    int sink = 2 * N + 1;
    Graph G(2 * N);
    int out, in;

    // Citirea datelor și construirea grafului
    for (int i = 1; i <= N; i++) {
        f >> out >> in;
        G.AddEdge(source, i, out);
        G.AddEdge(N + i, sink, in);
        for (int j = 1; j <= N; j++)
            if (i != j)
                G.AddEdge(i, N + j, 1);
    }

    // Calculul fluxului maxim și afișarea drumurilor rezultate
    g << G.EdmondsKarp(source, sink) << endl;
    G.Roads();

    return 0;
}