Cod sursa(job #3190264)

Utilizator ChelaruPaulChelaru Paul ChelaruPaul Data 7 ianuarie 2024 13:47:56
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.68 kb
#include <bits/stdc++.h>
using namespace std;

ifstream inputFile("harta.in");
ofstream outputFile("harta.out");

// Matrice de capacități și matrice de fluxuri
int capacityMatrix[1001][1001], flowMatrix[1001][1001];

// Vector pentru a stoca părinții în timpul BFS
vector<int> parentVector;

// Listă de adiacență pentru a reprezenta graful
vector<int> adjacencyList[1001];

int numberOfCities;

// BFS pentru a găsi căi de creștere
int bfs(int start, int end) {

    // Folosim o coadă și un vector de vizitare
    deque<int> queue;
    vector<bool> visited(end + 1, false);

    // Inițializăm vectorul de părinți
    parentVector.assign(end + 1, 0);

    queue.push_back(start);
    visited[start] = true;

    while (!queue.empty()) {
        int currentNode = queue.front();
        queue.pop_front();

        // Dacă am ajuns la destinație, ieșim din BFS
        if (currentNode == end) break;

        // Parcurgem vecinii nodului curent
        for (int i = 0; i < adjacencyList[currentNode].size(); i++) {
            int neighbor = adjacencyList[currentNode][i];

            // Dacă capacitatea muchiei este mai mare decât fluxul curent
            // Adăugăm nodul în coadă
            if (!visited[neighbor] && capacityMatrix[currentNode][neighbor] > flowMatrix[currentNode][neighbor]) {
                queue.push_back(neighbor);

                // Păstrăm nodul anterior în vectorul de părinți
                // Pentru a reconstrui calea ulterior
                parentVector[neighbor] = currentNode;
                visited[neighbor] = true;
            }
        }
    }

    // Dacă am ajuns la destinație (am găsit o cale de creștere), returnăm 1
    // Altfel, returnăm 0
    if (parentVector[end]) return 1;
    return 0;
}

// Algoritmul lui Edmonds-Karp pentru a găsi fluxul maxim
int edmondsKarp(int start, int end) {
    int maxFlow = 0;
    int current, minFlow;

    while (bfs(start, end)) {
        minFlow = INT_MAX;
        current = end;

        // Determinăm fluxul minim pe calea de creștere,
        // Comparând fluxul dintre nodul curent și părintele său cu fluxul minim curent
        while (current != 0) {
            if ((capacityMatrix[parentVector[current]][current] - flowMatrix[parentVector[current]][current]) < minFlow)
                minFlow = (capacityMatrix[parentVector[current]][current] - flowMatrix[parentVector[current]][current]);

            current = parentVector[current];
        }

        current = end;

        // Actualizăm fluxurile pe cale
        while (current != 0) {
            // Fluxul crește pe muchiile directe și scade pe cele inverse
            flowMatrix[parentVector[current]][current] += minFlow;
            flowMatrix[current][parentVector[current]] -= minFlow;

            current = parentVector[current];
        }

        // Adăugăm fluxul minim la fluxul total
        maxFlow += minFlow;
    }

    return maxFlow;
}

int main() {
    int startNode, endNode, outDegree, inDegree;

    inputFile >> numberOfCities;

    startNode = 0;
    endNode = numberOfCities + numberOfCities + 1;

    // Construim graf și matricea de capacități
    for (int city = 1; city <= numberOfCities; city++) {
        inputFile >> outDegree >> inDegree;

        adjacencyList[startNode].push_back(city);
        adjacencyList[city].push_back(startNode);
        capacityMatrix[startNode][city] = outDegree;

        int auxiliaryNode = numberOfCities + city;
        adjacencyList[auxiliaryNode].push_back(endNode);
        adjacencyList[endNode].push_back(auxiliaryNode);
        capacityMatrix[auxiliaryNode][endNode] = inDegree;
    }

    // Adăugăm muchii între orașe cu constrângerile specificate
    // 1. nu putem merge din oras in el insusi
    // 2. nu putem avea muchia i-j daca avem deja muchia j-i
    for (int city1 = 1; city1 <= numberOfCities; city1++) {
        for (int city2 = numberOfCities + 1; city2 <= numberOfCities + numberOfCities; city2++) {
            if ((city1 % numberOfCities) != (city2 % numberOfCities)) {
                adjacencyList[city1].push_back(city2);
                adjacencyList[city2].push_back(city1);
                capacityMatrix[city1][city2] = 1;
            }
        }
    }

    // Găsim și afișăm fluxul maxim
    outputFile << edmondsKarp(startNode, endNode) << endl;

    // Afișăm drumurile selectate în fluxul maxim
    for (int city1 = 1; city1 <= numberOfCities; city1++) {
        for (int city2 = numberOfCities + 1; city2 <= numberOfCities + numberOfCities; city2++) {
            if (flowMatrix[city1][city2] == 1)
                outputFile << city1 << ' ' << city2 - numberOfCities << endl;
        }
    }

    inputFile.close();
    outputFile.close();

    return 0;
}