Cod sursa(job #3190255)

Utilizator adelibdAdel Ib adelibd Data 7 ianuarie 2024 13:34:24
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.97 kb
#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;
}