Pagini recente » Cod sursa (job #2366199) | Cod sursa (job #258402) | Cod sursa (job #2125580) | Cod sursa (job #2652560) | Cod sursa (job #2962173)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
vector<vector<int>> la;
int n, nr, src, dest, nrDrumuri;
int cap[205][205];
bool vizitat[205];
int flux[205][205];
int tata[205];
int bfs() {
queue<int> coada;
for (int i = 0; i < nr; i++) {
vizitat[i] = false;
}
vizitat[src] = true;
coada.push(src);
while (!coada.empty()) {
int nod = coada.front();
coada.pop();
for (auto vecin : la[nod]) {
if (!vizitat[vecin] && flux[nod][vecin] < cap[nod][vecin]) {
vizitat[vecin] = true;
tata[vecin] = nod;
coada.push(vecin);
if (vecin == dest)
return 1;
}
}
}
return 0;
}
int fluxMinRamas(int nod) {
if (nod == src)
return INT32_MAX;
int nodTata = tata[nod];
int flx = cap[nodTata][nod] - flux[nodTata][nod];
return min(flx, fluxMinRamas(nodTata));
}
void actualizareFlux(int nod) {
if (nod == src)
return;
int nodTata = tata[nod];
flux[nodTata][nod] += 1;
flux[nod][nodTata] -= 1;
actualizareFlux(nodTata);
}
int main() {
fin >> n;
nr = 2 * n + 2;
src = 0;
dest = nr - 1;
la.resize(nr);
for (int i = 1; i <= n; i++) {
int x, y;
fin >> x >> y;
cap[src][i] = x;
cap[i + n][dest] = y;
}
//formam muchiile
for (int i = 1; i <= n; i++) {
la[src].push_back(i);
la[i].push_back(src);
}
for (int i = n + 1; i < nr - 1; i++) {
la[i].push_back(dest);
la[dest].push_back(i);
}
for (int i = 1; i <= n; i++) {
for (int j = n + 1; j < nr - 1; j++) {
if (j - i == n)
continue;
la[i].push_back(j);
la[j].push_back(i);
cap[i][j] = 1;
}
}
while (bfs()) {
for (auto vecin : la[dest]) {
if (!vizitat[vecin] || fluxMinRamas(dest) == 0)
continue;
nrDrumuri++;
actualizareFlux(dest);
}
}
fout << nrDrumuri << endl;
for (int i = 1; i <= n; i++) {
for (int j = n + 1; j < nr; j++) {
if (flux[i][j] == 1)
fout << i << " " << j - n << endl;
}
}
}