Cod sursa(job #3190522)

Utilizator Andreeamiruna27Mindrescu Andreea Andreeamiruna27 Data 7 ianuarie 2024 17:49:12
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.6 kb
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <climits>

using namespace std;

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

int N, x, y, roadways;
vector<vector<int>> adjacencyList, capacity, flow;
int source, sink;
vector<int> previous;

void initializePrevious() {
    for (int i = 0; i <= sink; i++) {
        previous[i] = -1;
    }
}

int bfs() {
    initializePrevious();

    queue<pair<int, int>> q;
    q.push({0, INT_MAX});

    while (!q.empty()) {
        int town = q.front().first, minFlowUntilNow = q.front().second;
        q.pop();
        for (auto& nextTown : adjacencyList[town]) {
            if (previous[nextTown] == -1 && capacity[town][nextTown] > flow[town][nextTown]) {
                previous[nextTown] = town;
                int residualFlow = capacity[town][nextTown] - flow[town][nextTown];
                int minimumFlowOfPath = minFlowUntilNow > residualFlow ? residualFlow : minFlowUntilNow;
                q.push({nextTown, minimumFlowOfPath});

                if (nextTown == sink) return minimumFlowOfPath;
            }
        }
    }
    return 0;
}

void edmondsKarp() {
    int town, prevTown;
    while (true) {
        int flowOfPath = bfs();
        if (!flowOfPath) break;

        town = sink;

        while (source != town) {
            prevTown = previous[town];

            flow[town][prevTown] -= flowOfPath;
            flow[prevTown][town] += flowOfPath;

            town = previous[town];
        }
    }
}

void readData() {
    inputFile >> N;
    sink = 2 * N + 1;
    previous.resize(sink);
    adjacencyList.resize(sink + 1, {});
    capacity.assign(sink + 1, vector<int>(sink + 1));
    flow.resize(sink + 1, vector<int>(sink + 1));

    for (int i = 1; i <= N; i++) {
        inputFile >> x >> y;
        roadways += x;
        for (int j = N + 1; j < sink; j++) {
            if (i != j - N) {
                adjacencyList[j].push_back(i);
                adjacencyList[i].push_back(j);
                capacity[i][j] = 1;
            }
        }
        capacity[source][i] = x;
        capacity[i + N][sink] = y;
        adjacencyList[source].push_back(i);
        adjacencyList[i].push_back(source);
        adjacencyList[i + N].push_back(sink);
        adjacencyList[sink].push_back(i + N);
    }
}

void solve() {
    readData();
    outputFile << roadways << endl;
    edmondsKarp();

    for (int i = 1; i <= N; i++) {
        for (int j = N + 1; j < sink; j++) {
            if (flow[i][j]) {
                outputFile << i << " " << j - N << endl;
            }
        }
    }
}

int main() {
    solve();
    return 0;
}