Pagini recente » Cod sursa (job #1884500) | Cod sursa (job #1821032) | Cod sursa (job #2141427) | Cod sursa (job #665021) | Cod sursa (job #3191968)
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
int numarorase, i, drumuriiesire, drumuriintrare, vecin, destinatie, minim, nodcurent, numardrumuri, j;
int capacitate[205][205], flux[205][205], s[205], t[205];
vector<int> listavecini[205];
bitset<205> vizitat;
ifstream fin("abce.in");
ofstream fout("abce.out");
int bfs() {
int inceput, final, nod, vecin, i;
int existadrumcrestere = 0;
vizitat.reset();
inceput = final = 1;
t[0] = -1;
s[1] = 0;
vizitat[0] = 1;
// bfs pentru a gasi un drum de creștere
while (inceput <= final) {
nod = s[inceput];
for (i = 0; i < listavecini[nod].size(); i++) {
vecin = listavecini[nod][i];
if (vizitat[vecin] == 0 && flux[nod][vecin] < capacitate[nod][vecin]) {
vizitat[vecin] = 1;
final++;
s[final] = vecin;
t[vecin] = nod;
if (vecin == destinatie) {
existadrumcrestere = 1;
}
}
}
inceput++;
}
return existadrumcrestere;
}
int main() {
fin >> numarorase;
destinatie = 2 * numarorase + 1;
// construirea grafului
for (i = 1; i <= numarorase; i++) {
fin >> drumuriiesire >> drumuriintrare;
listavecini[0].push_back(i);
listavecini[i].push_back(0);
capacitate[0][i] = drumuriiesire;
listavecini[numarorase + i].push_back(destinatie);
listavecini[destinatie].push_back(numarorase + i);
capacitate[numarorase + i][destinatie] = drumuriintrare;
}
// adaugarea muchiilor pentru graf complet bipartit
for (i = 1; i <= numarorase; i++) {
for (j = numarorase + 1; j <= 2 * numarorase; j++) {
if (j != numarorase + i) {
listavecini[i].push_back(j);
listavecini[j].push_back(i);
capacitate[i][j] = 1;
}
}
}
// algoritmul edmonds-karp
while (bfs()) {
for (i = 0; i < listavecini[destinatie].size(); i++) {
vecin = listavecini[destinatie][i];
if (vizitat[vecin] == 1 && flux[vecin][destinatie] < capacitate[vecin][destinatie]) {
minim = capacitate[vecin][destinatie] - flux[vecin][destinatie];
nodcurent = vecin;
while (t[nodcurent] >= 0) {
minim = min(minim, capacitate[t[nodcurent]][nodcurent] - flux[t[nodcurent]][nodcurent]);
nodcurent = t[nodcurent];
}
// actualizarea fluxului și capacitaților
flux[vecin][destinatie] += minim;
flux[destinatie][vecin] -= minim;
nodcurent = vecin;
while (t[nodcurent] >= 0) {
flux[t[nodcurent]][nodcurent] += minim;
flux[nodcurent][t[nodcurent]] -= minim;
nodcurent = t[nodcurent];
}
}
}
}
// nr de drumuri
numardrumuri = 0;
for (i = 1; i <= numarorase; i++) {
for (j = numarorase + 1; j <= 2 * numarorase; j++) {
if (flux[i][j] == 1) {
numardrumuri++;
}
}
}
fout << numardrumuri << "\n";
// afis
for (i = 1; i <= numarorase; i++) {
for (j = numarorase + 1; j <= 2 * numarorase; j++) {
if (flux[i][j] == 1) {
fout << i << " " << j - numarorase << "\n";
}
}
}
fin.close();
fout.close();
return 0;
}