Pagini recente » Cod sursa (job #711298) | Cod sursa (job #1329314) | Cod sursa (job #2031264) | Cod sursa (job #452571) | Cod sursa (job #2684985)
#include <iostream>
#include <fstream>
#include <unordered_map>
#include <queue>
#include <vector>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
const int INF = 1000000000;
int n_nodes;
int * g_in;
int * g_out;
vector <pair <int, int>> m_list;
int n;
unordered_map <int, int> * lv;
bool BFS(int t[]){
bool * viz = new bool [n + 1];
t[1] = 0;
for(int i = 1; i <= n; i++)
viz[i] = 0;
viz[1] = 1;
queue <int> q;
q.push(1);
while(!q.empty()){
int current_node = q.front();
q.pop();
for(auto & next : lv[current_node]){
if(next.first == n){
t[n] = current_node;
return 0;
}
else if(!viz[next.first]){
t[next.first] = current_node;
viz[next.first] = 1;
q.push(next.first);
}
}
}
return 1;
}
void Edmonds_Karp(){
bool path_not_found;
int * t = new int [n + 1];
do{
path_not_found = BFS(t);
if(!path_not_found){
/// prima iteratie prin vectorul de tati, pentru a determina muchia de capacitate minima
int min_capacity = INF;
int node = n;
while(t[node]){
int current_capacity = lv[t[node]][node];
if(current_capacity < min_capacity)
min_capacity = current_capacity;
node = t[node];
}
/// a doua iteratie pentru a modifica graful rezidual
node = n;
while(t[node]){
int current_capacity = lv[t[node]][node];
if(current_capacity == min_capacity){
lv[t[node]].erase(node);
}
else
lv[t[node]][node] -= min_capacity;
if(lv[node].find(t[node]) != lv[node].end()){
lv[node][t[node]] += min_capacity;
}
else
lv[node][t[node]] = min_capacity;
node = t[node];
}
}
}
while(!path_not_found);
}
int main(){
f >> n_nodes;
g_in = new int [n_nodes + 1];
g_out = new int [n_nodes + 1];
int x, y;
for(int i = 1; i <= n_nodes; i++){
f >> x >> y;
g_out[i] = x;
g_in[i] = y;
}
/// pregatire apelare edmonds karp
/// cate o clona pentru fiecare nod, plus un nod de start si unul de final
/// voi avea codificarea:
/// 1 -> nodul sursa
/// 2 .. n_nodes + 1 -> primul rand de noduri
/// n_nodes + 2 .. n_nodes + n_nodes + 1 -> al doilea rand de noduri
/// n_nodes * 2 + 2 -> nodul destinatie
n = 2 + n_nodes * 2;
lv = new unordered_map <int, int> [n + 1]; ///lista de vecini in noul graf
for(int node = 2; node <= n_nodes + 1; node++){
if(g_out[node - 1])
lv[1][node] = g_out[node - 1];
for(int clone = n_nodes + 2; clone <= n_nodes + n_nodes + 1; clone++){
if(clone - n_nodes != node)
lv[node][clone] = 1;
}
if(g_in[node - 1])
lv[node + n_nodes][n_nodes * 2 + 2] = g_in[node - 1];
}
Edmonds_Karp();
for(int clone = n_nodes + 2; clone <= n_nodes + n_nodes + 1; clone++){
for(auto & node : lv[clone]){
m_list.push_back(pair <int, int> (node.first, clone - n_nodes));
}
}
g << m_list.size() << '\n';
for(int i = 0; i < m_list.size(); i++)
g << m_list[i].first - 1 << " " << m_list[i].second - 1 << '\n';
return 0;
}