Cod sursa(job #3188760)

Utilizator willOcanaru Mihai will Data 3 ianuarie 2024 19:55:18
Problema Taramul Nicaieri Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.77 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>

using namespace std;

#define MAX_N 105
#define MAX_M 10005
#define LARGE_NUMBER 1e9

ifstream input("harta.in");
ofstream output("harta.out");

int n, dist[MAX_M], parent[MAX_M], capacity[MAX_M][MAX_M];
vector<pair<int, int>> roads;
vector<int> cities[MAX_N + 5];


bool dijkstra() {

    for(int i = 0; i < MAX_M; ++i)
        dist[i] = LARGE_NUMBER;
    for(int i = 0; i < MAX_M; ++i)
        parent[i] = 0;

    queue<int> q;
    q.push(0);
    dist[0] = 0;

    // Perform BFS until the destination is reached 
    while (!q.empty()) {
        int current = q.front();
        q.pop();

        // or no more augmenting paths are found
        if (current == 2 * n + 1)
            break;

        for (auto next : cities[current]) {
            // If there is capacity on the edge and the new path is shorter
            if (capacity[current][next] && dist[next] > dist[current] + 1) {
                dist[next] = dist[current] + 1;
                parent[next] = current;
                q.push(next);
            }
        }
    }

    // no augmenting path is found
    if (dist[2 * n + 1] >= LARGE_NUMBER)
        return false;

    int flow = LARGE_NUMBER;

    // Find the minimum capacity on the augmenting path
    for (int current = 2 * n + 1; current; current = parent[current])
        flow = min(flow, capacity[parent[current]][current]);

    // Update the residual graph along the augmenting path
    for (int current = 2 * n + 1; current; current = parent[current]) {
        capacity[parent[current]][current] -= flow;
        capacity[current][parent[current]] += flow;
    }

    return true;
}


void buildGraph() {

    for (int i = 1; i <= n; ++i) {
        int outRoads, inRoads;
        input >> outRoads >> inRoads;

        cities[0].push_back(i);
        cities[i].push_back(0);
        capacity[0][i] = outRoads;

        cities[i + n].push_back(2 * n + 1);
        cities[2 * n + 1].push_back(i + n);
        capacity[i + n][2 * n + 1] = inRoads;
    }

    // Add edges between cities
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (i != j) {
                cities[i].push_back(j + n);
                cities[j + n].push_back(i);
                capacity[i][j + n] = 1;
            }
        }
    }
}


void findRoads() {
    while (dijkstra());

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (i != j && !capacity[i][j + n]) {
                roads.push_back({i, j});
            }
        }
    }
}

int main() {
    input >> n;
    buildGraph();
    findRoads();

    output << roads.size() << '\n';

    for (auto road : roads) {
        output << road.first << ' ' << road.second << '\n';
    }

    return 0;
}