Cod sursa(job #3189908)

Utilizator vatau.lorenaVatau Lorena vatau.lorena Data 6 ianuarie 2024 17:35:46
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.38 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>

const int MAX_VAL = 0x3f3f3f3f;
int nodes, capacity[220][220], parent[220], flow[220][220], max_flow;

// Funcția care calculează fluxul maxim folosind algoritmul Edmonds-Karp.
void maxFlow(int source, int destination);

// Funcția care parcurge graful folosind BFS pentru a identifica un drum de creștere.
bool bfs(int source, int destination);

// Funcție utilitară pentru a găsi minimul dintre două valori.
int findMin(int a, int b);

int main() {
    // Deschidere fișiere pentru citire și scriere.
    std::ifstream fin("harta.in");
    std::ofstream fout("harta.out");

    // Citirea numărului de noduri din fișier.
    fin >> nodes;
    int startVal, endVal;
    for (int i = 1; i <= nodes; ++i) {
        // Citirea valorilor pentru fiecare nod și inițializarea capacităților.
        fin >> startVal >> endVal;
        capacity[0][i] = startVal;
        capacity[i + nodes][2 * nodes + 1] = endVal;
        for (int j = nodes + 1; j <= 2 * nodes; ++j) {
            capacity[i][j] = 1;
        }
        capacity[i][i + nodes] = 0;  // Inițializare fluxuri.
    }

    // Apelul funcției pentru calculul fluxului maxim.
    maxFlow(0, 2 * nodes + 1);

    // Calcularea numărului de muchii care transportă flux.
    int result = 0;
    for (int i = 1; i <= nodes; ++i) {
        for (int j = 1; j <= nodes; ++j) {
            if (flow[i][j + nodes]) {
                ++result;
            }
        }
    }

    // Scrierea rezultatelor în fișierul de ieșire.
    fout << result << "\n";
    for (int i = 1; i <= nodes; ++i) {
        for (int j = 1; j <= nodes; ++j) {
            if (flow[i][j + nodes]) {
                fout << i << " " << j << "\n";
            }
        }
    }

    // Închiderea fișierelor.
    fin.close();
    fout.close();
    return 0;
}

// Implementarea funcției pentru calculul fluxului maxim.
void maxFlow(int source, int destination) {
    max_flow = 0;
    while (bfs(source, destination)) {
        int min_flow = MAX_VAL;
        int current = destination;
        while (current != source) {
            min_flow = findMin(min_flow, capacity[parent[current]][current] - flow[parent[current]][current]);
            current = parent[current];
        }

        current = destination;
        while (current != source) {
            flow[parent[current]][current] += min_flow;
            flow[current][parent[current]] -= min_flow;
            current = parent[current];
        }
        max_flow += min_flow;
    }
}

// Implementarea funcției BFS pentru parcurgerea grafului.
bool bfs(int source, int destination) {
    std::queue<int> q;
    memset(parent, -1, sizeof(parent));
    parent[source] = -2;
    q.push(source);

    while (!q.empty()) {
        int current = q.front();
        q.pop();
        for (int i = 0; i <= 2 * nodes + 1; ++i) {
            if (parent[i] == -1 && capacity[current][i] > flow[current][i]) {
                parent[i] = current;
                q.push(i);
                if (i == destination) {
                    return true;
                }
            }
        }
    }
    return false;
}

// Implementarea funcției utilitare pentru găsirea minimului dintre două valori.
int findMin(int a, int b) {
    return (a < b) ? a : b;
}