Cod sursa(job #3193462)

Utilizator sara_ionescu21Ionescu Sara sara_ionescu21 Data 14 ianuarie 2024 17:46:08
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.24 kb
#include <fstream>
#include <vector>
#include <queue>
#include <limits>
#include <algorithm>

using namespace std;

ifstream input_stream("harta.in");
ofstream output_stream("harta.out");

vector<vector<int>> city_network;
vector<vector<int>> city_flow;
vector<int> path_parents;
vector<bool> visited_cities;

void loadMapData(int& num_cities, int& start_point, int& end_point) {
    input_stream >> num_cities;
    start_point = 2 * num_cities;
    end_point = 2 * num_cities + 1;
    city_network.assign(2 * num_cities + 2, vector<int>(2 * num_cities + 2, 0));
    city_flow.assign(2 * num_cities + 2, vector<int>(2 * num_cities + 2, 0));

    path_parents.assign(2 * num_cities + 2, -1);
    visited_cities.assign(2 * num_cities + 2, false);

    for (int i = 0; i < num_cities; ++i) {
        int outgoing, incoming;
        input_stream >> outgoing >> incoming;
        city_network[start_point][i] = outgoing;
        city_network[i + num_cities][end_point] = incoming;
        for (int j = 0; j < num_cities; ++j) {
            if (i != j) {
                city_network[i][num_cities + j] = 1;
            }
        }
    }
}

bool searchForPath(int start_point, int end_point) {
    fill(begin(visited_cities), end(visited_cities), false);
    queue<int> city_queue;
    city_queue.push(start_point);
    visited_cities[start_point] = true;

    while (!city_queue.empty()) {
        int current_city = city_queue.front();
        city_queue.pop();

        for (int i = 0; i <= end_point; ++i) {
            if (!visited_cities[i] && city_network[current_city][i] - city_flow[current_city][i] > 0) {
                path_parents[i] = current_city;
                visited_cities[i] = true;
                city_queue.push(i);

                if (i == end_point) return true;
            }
        }
    }

    return false;
}

void exportMapRoutes(int num_cities, int max_flow) {
    output_stream << max_flow << endl;
    for (int i = 0; i < num_cities; ++i) {
        for (int j = 0; j < num_cities; ++j) {
            if (city_flow[i][num_cities + j] >
                0) {
                output_stream << i + 1 << " " << j + 1 << endl;
            }
        }
    }
}

int main() {
    int num_cities, start_point, end_point;
    loadMapData(num_cities, start_point, end_point);

    int max_flow = 0;

    while (searchForPath(start_point, end_point)) {
        int min_capacity = numeric_limits<int>::max();

        for (int city = end_point; city != start_point; city = path_parents[city]) {
            int prev_city = path_parents[city];
            min_capacity = min(min_capacity, city_network[prev_city][city] - city_flow[prev_city][city]);
        }

        for (int city = end_point; city != start_point; city = path_parents[city]) {
            int prev_city = path_parents[city];
            city_flow[prev_city][city] += min_capacity;
            city_flow[city][prev_city] -= min_capacity;
        }

        max_flow += min_capacity;

        fill(begin(visited_cities), end(visited_cities), false);
        fill(begin(path_parents), end(path_parents), -1);
    }

    exportMapRoutes(num_cities, max_flow);

    input_stream.close();
    output_stream.close();
    return 0;
}