Pagini recente » Cod sursa (job #2290987) | Cod sursa (job #1110030) | Cod sursa (job #1890144) | Cod sursa (job #2037192) | Cod sursa (job #2956804)
/*
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;
}