Cod sursa(job #3191967)

Utilizator az234as arf az234 Data 11 ianuarie 2024 05:32:24
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.61 kb
#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;
}