Pagini recente » Cod sursa (job #1089695) | Cod sursa (job #1280789) | Cod sursa (job #460116) | Cod sursa (job #3199191) | Cod sursa (job #3189382)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream input("harta.in");
ofstream output("harta.out");
const int MAX_N = 202;
int nod_sursa, nod_destinatie;
vector<vector<int>> flux(MAX_N, vector<int>(MAX_N, 0));
vector<vector<int>> capacitate(MAX_N, vector<int>(MAX_N, 0));
vector<int> flux_temporar(MAX_N, 0);
// vector de tati
vector<int> parinti(MAX_N, -1);
// matricea de adiacenta
vector<vector<int>> vecini(MAX_N);
queue<int> coada_bfs;
/*
Aceasta functie cauta efectiv path uri
adiacente care pot imbunatati flow ul.
*/
int BFS() {
fill(parinti.begin(), parinti.end(), -1);
parinti[nod_sursa] = 0;
fill(flux_temporar.begin(), flux_temporar.end(), 0);
while (!coada_bfs.empty()) coada_bfs.pop();
coada_bfs.push(nod_sursa);
flux_temporar[nod_sursa] = 10000;
while (!coada_bfs.empty()) {
int curent = coada_bfs.front();
coada_bfs.pop();
for (int vecin : vecini[curent]) {
if (parinti[vecin] == -1 && capacitate[curent][vecin] - flux[curent][vecin] > 0) {
parinti[vecin] = curent;
flux_temporar[vecin] = min(flux_temporar[curent], (capacitate[curent][vecin] - flux[curent][vecin]));
if (vecin == nod_destinatie)
return flux_temporar[nod_destinatie];
coada_bfs.push(vecin);
}
}
}
return 0;
}
int main() {
int num_orase;
input >> num_orase;
nod_destinatie = 2 * num_orase + 1;
// aici creem flow ul initial
for (int i = 1; i <= num_orase; i++) {
int iesire, intrare;
input >> iesire >> intrare;
capacitate[nod_sursa][i] = iesire;
capacitate[i + num_orase][nod_destinatie] = intrare;
vecini[nod_sursa].push_back(i);
vecini[num_orase + i].push_back(nod_destinatie);
for (int j = num_orase + 1; j <= num_orase * 2; j++) {
if (j != i + num_orase) {
capacitate[i][j] = 1;
vecini[i].push_back(j);
vecini[j].push_back(i);
}
}
}
int flux_maxim = 0;
fill(flux.begin(), flux.end(), vector<int>(MAX_N, 0));
// Ford-Fulkerson
while (true) {
int flux_curent = BFS();
if (flux_curent == 0)
break;
flux_maxim += flux_curent;
int nod_curent = nod_destinatie;
while (nod_curent != nod_sursa) {
flux[parinti[nod_curent]][nod_curent] += flux_curent;
flux[nod_curent][parinti[nod_curent]] -= flux_curent;
nod_curent = parinti[nod_curent];
}
}
output << flux_maxim << endl;
for (int i = 1; i <= num_orase; i++)
for (int j = 1 + num_orase; j <= num_orase * 2; j++)
if (flux[i][j])
output << i << ' ' << j - num_orase << endl;
return 0;
}