Cod sursa(job #3188832)

Utilizator RaducusCaracas Radu Nicolae Raducus Data 3 ianuarie 2024 21:44:23
Problema Taramul Nicaieri Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.81 kb
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <fstream>
#include <cstring>
using namespace std;

const int MAX_N = 1005;
ifstream f("harta.in");
ofstream fout("harta.out");

struct Edge {
    int v, capacity, flowPassed;
};

vector<vector<Edge>> graph(MAX_N * 2 + 2);
vector<int> parent(MAX_N * 2 + 2);
bool bfs(int s, int t) {
    fill(parent.begin(), parent.end(), -1);
    vector<bool> visited(graph.size(), false);
    queue<int> q;
    q.push(s);
    visited[s] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout<<u<<" ";
        for (auto &edge : graph[u]) {
            int v = edge.v;
            // Verifică dacă nodul nu a fost vizitat și dacă există capacitate disponibilă
            if (!visited[v] && edge.capacity - edge.flowPassed > 0) {
                q.push(v);
                parent[v] = u;
                visited[v] = true;
                if (v == t) {
                    return true; // Calea a fost găsită
                }
            }
        }
    }

    return false; // Nu s-a găsit nicio cale
}

int edmondsKarp(int s, int t) {
    int max_flow = 0;

    while (bfs(s, t)) {
        int path_flow = INT_MAX;

        // Determinați fluxul maxim pe calea găsită
        for (int v = t; v != s; v = parent[v]) {
            int u = parent[v];
            for (auto &edge : graph[u]) {
                if (edge.v == v && edge.capacity - edge.flowPassed > 0) {
                    path_flow = min(path_flow, edge.capacity - edge.flowPassed);
                    break;
                }
            }
        }

        cout << "Calea gasita cu flux: " << path_flow << endl;

       // Actualizăm capacitatea rămasă și fluxul trecut pe muchii și muchiile inverse
        for (int v = t; v != s; v = parent[v]) {
            int u = parent[v];
            // Căutăm muchia directă și inversă pentru a actualiza fluxul
            for (auto &edge : graph[u]) {
                if (edge.v == v) {
                    edge.flowPassed += path_flow; // Actualizare muchie directă
                    // Căutăm și actualizăm muchia inversă
                    for (auto &backEdge : graph[v]) {
                        if (backEdge.v == u) {
                            backEdge.flowPassed -= path_flow; // Actualizare muchie inversă
                            break;
                        }
                    }
                    break;
                }
            }
        }
        max_flow += path_flow;
    }

    return max_flow;
}


int main() {
    int N; // Numărul de orașe
    f >> N;

    int source = 0; // Nodul sursă
    int sink = 2 * N + 1; // Nodul destinație

    // Construirea graficului
    for (int i = 1; i <= N; ++i) {
        int out, in;
        f >> out >> in;

        // De la sursă la orașul de plecare
        graph[source].push_back({i, out, 0});

        // De la orașul de sosire la destinație
        graph[N + i].push_back({sink, in, 0});
    }

    // Muchii între orașele de plecare și sosire
    for (int i = 1; i <= N; ++i) {
        for (int j = N + 1; j <= 2 * N; ++j) {
            if (i != j - N) {
                graph[i].push_back({j, 1, 0}); // Adaugă muchia cu capacitatea 1
            }
        }
    }

    // Aplicarea algoritmului Edmonds-Karp pentru a găsi fluxul maxim
    int maxFlow = edmondsKarp(source, sink);

   
// Interpretăm rezultatele pentru a găsi drumurile individuale
    fout << maxFlow << endl;
    for (int i = 1; i <= N; ++i) {
        for (auto &edge : graph[i]) {
            if (edge.v > N && edge.v <= 2 * N && edge.flowPassed > 0) {
                fout << i << " " << (edge.v - N) << endl;
            }
        }
    }

    return 0;
}