Pagini recente » Cod sursa (job #1259068) | Cod sursa (job #190922) | Cod sursa (job #551720) | Cod sursa (job #758563) | Cod sursa (job #3190255)
#include <fstream>
#include <vector>
#include <fstream>
#include <iostream>
#include <queue>
std::ifstream fin("harta.in");
std::ofstream fout("harta.out");
//std::ifstream fin("C:\\Users\\DellMX\\CLionProjects\\bfs-dfs\\harta.in");
//std::ofstream fout("C:\\Users\\DellMX\\CLionProjects\\bfs-dfs\\harta.out");
int matrCapacitate[300][300];
int matrFlux[300][300];
std::vector<int> vecini[300];
std::vector<bool> vizitat;
std::vector<int> parinti(300);
int n, x, y, nrMuchii, dst;
int bfs() {
std::queue<int> q;
vizitat.assign(300, false);
vizitat[0] = 1;
q.push(0);
while (!q.empty()) {
int nodCurent = q.front();
q.pop();
for (auto &vecin : vecini[nodCurent]) {
if (vizitat[vecin] == false && matrCapacitate[nodCurent][vecin] > matrFlux[nodCurent][vecin]) {
q.push(vecin);
vizitat[vecin] = true;
parinti[vecin] = nodCurent;
if (vecin == dst) {
return 1;
}
}
}
}
return 0;
}
int main() {
fin >> n;
dst = 2 * n + 1;
nrMuchii = 0;
for (int i = 1; i <= n; i++) {
vecini[0].push_back(i);
vecini[i].push_back(0);
}
for (int i = n + 1; i < dst; i++) {
vecini[dst].push_back(i);
vecini[i].push_back(dst);
}
for (int i = 1; i <= n; i++) {
for (int j = n + 1; j < dst; j++) {
if (i + n != j) {
vecini[i].push_back(j);
vecini[j].push_back(i);
matrCapacitate[i][j] = 1;
}
}
}
for (int i = 1; i <= n; i++) {
fin >> x >> y;
nrMuchii += x;
matrCapacitate[0][i] = x;
matrCapacitate[n + i][dst] = y;
}
std::cout << nrMuchii << "\n";
fout << nrMuchii << "\n";
while (bfs()) {
for (auto &vecin : vecini[dst]) {
int diferenta = matrCapacitate[vecin][dst] - matrFlux[vecin][dst];
if (vizitat[vecin] == true && diferenta > 0) {
int nodCurent = vecin;
while (nodCurent != 0) {
diferenta = std::min(diferenta, matrCapacitate[parinti[nodCurent]][nodCurent] - matrFlux[parinti[nodCurent]][nodCurent]);
nodCurent = parinti[nodCurent];
}
matrFlux[vecin][dst] += diferenta;
matrFlux[dst][vecin] -= diferenta;
nodCurent = vecin;
while (nodCurent != 0) {
matrFlux[parinti[nodCurent]][nodCurent] += diferenta;
matrFlux[nodCurent][parinti[nodCurent]] -= diferenta;
nodCurent = parinti[nodCurent];
}
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = n + 1; j < dst; j++) {
if (matrFlux[i][j] == 1) {
std::cout << i << " " << j - n << "\n";
fout << i << " " << j - n << "\n";
}
}
}
return 0;
}