Pagini recente » Cod sursa (job #1832054) | Cod sursa (job #259375) | Cod sursa (job #2218484) | Cod sursa (job #1544821) | Cod sursa (job #3190495)
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;
ifstream f("../harta.in");
ofstream g("../harta.out");
int n, x, y, nr_drumuri;
vector<vector<int>> vecini, capacitati, flow;
int nod_sursa, nod_final;
vector<int> predecesor;
int bfs () {
for(int i=0; i <= nod_final; i++){
predecesor[i] = -1; //in vectorul predecesor salvam cel mai scurt drum gasit de bfs
}
queue<pair<int, int>> q; //pereche de nod-flow minim pana in acel punct
q.push({0, INT_MAX});
while (!q.empty()) {
int oras = q.front().first, flow_min_anterior = q.front().second;
q.pop();
for (auto& urm_oras : vecini[oras]) {
if (predecesor[urm_oras] == -1 && capacitati[oras][urm_oras] > flow[oras][urm_oras]) { // daca nu e vizitat deja si daca capacitatea permite sa mergem
predecesor[urm_oras] = oras;
int flow_min_actual = capacitati[oras][urm_oras] - flow[oras][urm_oras];
int flow_min;
if (flow_min_anterior > flow_min_actual) //actualizam flowul minim prin compararea flowului minim de la nodul anterior cu capacitatea residuala a nodului actual
flow_min=flow_min_actual;
//q.push({urm_oras,flow_min_actual});
else
flow_min=flow_min_anterior;
//q.push({urm_oras,flow_min_actual});
q.push({urm_oras, flow_min});
if (urm_oras == nod_final) return flow_min;
}
}
}
return 0;
}
void edmonds_karp () {
int oras_act, oras_ant;
while (true) {
int flow1 = bfs();
if (!flow1) break;
oras_act = nod_final;//parcurgem drumul gasit cu bfs in ordine inversa cu ajutorul vectorului predecesor
while (nod_sursa != oras_act) {
oras_ant = predecesor[oras_act];
flow[oras_act][oras_ant] -= flow1;
flow[oras_ant][oras_act] += flow1;
oras_act = predecesor[oras_act];
}
}
}
void citire_date () {
f >> n;
nod_final = 2 * n + 1;
predecesor.resize(nod_final);
vecini.resize(nod_final + 1, {});
capacitati.assign(nod_final + 1, vector<int>(nod_final + 1));
flow.resize(nod_final + 1, vector<int>(nod_final + 1));
for (int i=1; i <= n; i++) {
f>>x>>y;
nr_drumuri += x;
for (int j=1; j <= n; j++) {
if (i != j) {
vecini[j + n].push_back(i);
vecini[i].push_back(j + n);
capacitati[i][j + n] = 1;
}
}
capacitati[nod_sursa][i] = x;
capacitati[i + n][nod_final] = y;
vecini[nod_sursa].push_back(i);
vecini[i].push_back(nod_sursa);
vecini[i + n].push_back(nod_final);
vecini[nod_final].push_back(i + n);
}
}
int main () {
citire_date();
g << nr_drumuri << endl;
edmonds_karp();
for (int i=1; i <= n; i++) {
for (int j= n + 1; j < nod_final; j++) {
if (flow[i][j]) {
g << i << " " << j - n << endl;
}
}
}
return 0;
}