Cod sursa(job #2956804)

Utilizator AdelaCorbeanuAdela Corbeanu AdelaCorbeanu Data 20 decembrie 2022 17:48:43
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.28 kb
/*
    Dublam nodurile si aplicam algoritmul de cuplaj ce foloseste flux. Graful va arata
    in felul urmator: Nodul de start (0) este legat de nodul X (X <- 1..N) cu capacitatea
    gradului de iesire al lui X (deoarece aceste este numarul de muchii pe care X le primeste
    ca sa le "dea mai departe"); X este legat de toate dublurile nodurilor, cu exceptia
    dublurii lui, adica toate nodurile Y <- 1..N, X != Y, printr-o muchie de cost 1, deoarece
    X poate trimite in Y o singura muchie; Din fiecare dublura avem muchie catre nodul final de
    capacitate egala cu gradul de intrare al nodului respectiv (deoarece atatea muchii au fost duse
    SPRE el).

    Rulam algoritmul de determinare a fluxului maxim si rezultatul va fi cuplajul cautat, adica
    numarul de muchii pe care le-am trasat (egal de asemenea cu jumatate din suma tuturor gradelor).

    Vom considera nodurile initiale (1..N) si sursa (0) ca fiind in primul set, iar dublurile
    si destinatia in al doilea.
    Pentru a obtine muchiile ce alcatuiesc cuplajul, vom afisa muchiile care leaga un nod
    din primul set cu un nod din al doilea set si au capacitate 0 (adica le-am utilizat).
    Pentru reprezentarea grafului, am indexat nodurile astfel:
        -> nod start = 0
        -> nodurile: 1 .. n  (primul set)
        -> dublurile: n + 1 .. 2 * n (al doilea set)
        -> nod final = 2 * n + 1
 */

#include <bits/stdc++.h>

int flow_after_BFS (std::vector<std::vector<int>> &adj_list,
                    std::vector<std::vector<int>> &capacity,
                    std::vector<int> &previous) {

    int n = adj_list.size() - 1;
    std::vector<bool> sel(n + 1, false);
    std::queue<int> bf_queue;

    bf_queue.push(0);
    sel[0] = true;

    while (!bf_queue.empty()) {
        int current = bf_queue.front();
        bf_queue.pop();

        for (auto nbh : adj_list[current]) {
            if (!sel[nbh] && capacity[current][nbh] > 0 && nbh != n) {
                sel[nbh] = true;
                bf_queue.push(nbh);
                previous[nbh] = current;
            }
        }
    }

    int max_flow_possible = 0;

    for (auto nbh : adj_list[n]) {
        if (!sel[nbh]) continue;

        int current_path_flow = capacity[nbh][n];
        int current = nbh;
        while (current != 0) {
            current_path_flow = std::min(current_path_flow, capacity[previous[current]][current]);
            current = previous[current];
        }

        capacity[nbh][n] -= current_path_flow;
        capacity[n][nbh] += current_path_flow;
        current = nbh;
        while (current != 0) {
            capacity[previous[current]][current] -= current_path_flow;
            capacity[current][previous[current]] += current_path_flow;
            current = previous[current];
        }

        max_flow_possible += current_path_flow;
    }

    return max_flow_possible;
}

int get_max_flow (std::vector<std::vector<int>> &adj_list,
                  std::vector<std::vector<int>> &capacity) {
    int n = adj_list.size() - 1;
    std::vector<int> previous(n + 1, -1);

    int total_max_flow = 0;
    int path_flow = flow_after_BFS(adj_list, capacity, previous);
    while (path_flow) {
        total_max_flow += path_flow;
        path_flow = flow_after_BFS(adj_list, capacity, previous);
    }

    return total_max_flow;
}

int main()
{
    std::ifstream fin("harta.in");
    std::ofstream fout("harta.out");

    int n;
    fin >> n;

    std::vector<std::vector<int>> adj_list(2 * (n + 1));
    std::vector<std::vector<int>> capacity(2 * (n + 1), std::vector<int>(2 * (n + 1), 0));

    for (int i = 1; i <= n; ++i) {
        int out, in;
        fin >> out >> in;

        adj_list[0].push_back(i);
        adj_list[i].push_back(0);
        capacity[0][i] = out;

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

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

    fout << get_max_flow(adj_list, capacity) << '\n';
    for (int i = 1; i <= n; ++i)
        for (auto j : adj_list[i])
            if (!capacity[i][j] && j) fout << i << " " << j - n << '\n';

    return 0;
}