Pagini recente » Cod sursa (job #605769) | Cod sursa (job #10185) | Cod sursa (job #1176948) | Rating Barbulescu Daniel (1994) | Cod sursa (job #3190914)
#include <iostream>
#include <fstream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <deque>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
class Graph{
int n, nr_noduri, s, t;
int infinity = 1e8;
vector<int> parent;
vector<unordered_map<int, int>> adiac;
public:
Graph(){
f >> n;
nr_noduri = 2 * n + 2;
s = nr_noduri - 2;
t = nr_noduri - 1;
adiac.resize(nr_noduri);
int intrare, iesire;
for(int i = 0; i < n; i++){
f >> intrare >> iesire;
intrare; iesire;
adiac[s][i] = intrare;
adiac[i + n][t] = iesire;
for(int j = 0; j < n; j++){
if(i != j) {
adiac[i][n + j] = 1;
adiac[n + j][i] = 0;
}
}
}
}
int edmond_karp(){
parent.resize(nr_noduri, -1);
parent[s] = s;
bool still_running = true;
int total_flux = 0;
while(still_running){
still_running = false;
int curent_flux = bfs(s);
if(curent_flux > 0){
still_running = true;
total_flux += curent_flux;
}
}
return total_flux;
}
int bfs(int index){
vector<bool> visited(nr_noduri, false);
deque<pair<int, int>>coada; // nodul si fluxul cu care s-a ajuns in nod
coada.push_front({index, infinity});
visited[index] = true;
while(!coada.empty()) {
int nod = coada.front().first;
int flux = coada.front().second;
coada.pop_front();
for (auto &vec: adiac[nod]) {
if (!visited[vec.first] && vec.second > 0) {
parent[vec.first] = nod;
if(vec.first == t) {
flux = min(flux, vec.second);
rebalance(t, min(flux, vec.second));
return flux;
}
else{
visited[vec.first] = true;
if(vec.first < n)
coada.push_back({vec.first, min(flux, vec.second)});
else
coada.push_front({vec.first, min(flux, vec.second)});
}
}
}
}
return 0;
}
void rebalance(int index, int used_flux){
while(index != parent[index]){
adiac[parent[index]][index] -= used_flux;
adiac[index][parent[index]] += used_flux;
index = parent[index];
}
}
void used_edges(){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++)
if(i != j && adiac[i][j + n] == 0)
g << i + 1 << ' ' << j + 1 << '\n';
}
}
};
int main() {
Graph graf;
g << graf.edmond_karp() << '\n';
graf.used_edges();
return 0;
}