Cod sursa(job #3186168)

Utilizator Nicoleta114Caramaliu Nicoleta Nicoleta114 Data 21 decembrie 2023 20:33:04
Problema Taramul Nicaieri Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.97 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

ifstream intrare("harta.in");
ofstream iesire("harta.out");

struct Arc {
    int capacitate, flux;
};

class Graf {
public:
    Graf(int n);
    void adaugaArc(int deLa, int catre, int capacitate);
    int fluxMaxim(int sursa, int destinatie);
    const vector<vector<Arc>>& getMatriceAdiacenta() const;

private:
    vector<vector<Arc>> matriceAdiacenta;
    vector<int> parinte;

    bool bfs(int sursa, int destinatie);
};

Graf::Graf(int n) : matriceAdiacenta(2 * n + 2, vector<Arc>(2 * n + 2)), parinte(2 * n + 2) {}

void Graf::adaugaArc(int deLa, int catre, int capacitate) {
    matriceAdiacenta[deLa][catre].capacitate += capacitate;
}

bool Graf::bfs(int sursa, int destinatie) {
    fill(parinte.begin(), parinte.end(), -1);
    queue<int> q;
    q.push(sursa);
    parinte[sursa] = sursa;

    while (!q.empty()) {
        int curent = q.front();
        q.pop();

        for (int urmator = 0; urmator < matriceAdiacenta.size(); ++urmator) {
            if (parinte[urmator] == -1 && matriceAdiacenta[curent][urmator].capacitate - matriceAdiacenta[curent][urmator].flux > 0) {
                q.push(urmator);
                parinte[urmator] = curent;
            }
        }
    }

    return parinte[destinatie] != -1;
}

int Graf::fluxMaxim(int sursa, int destinatie) {
    int fluxMaxim = 0;

    while (bfs(sursa, destinatie)) {
        int capacitateMinima = INT_MAX;
        for (int curent = destinatie; curent != sursa; curent = parinte[curent]) {
            int anterior = parinte[curent];
            capacitateMinima = min(capacitateMinima,
                                   matriceAdiacenta[anterior][curent].capacitate - matriceAdiacenta[anterior][curent].flux);
        }

        for (int curent = destinatie; curent != sursa; curent = parinte[curent]) {
            int anterior = parinte[curent];
            matriceAdiacenta[anterior][curent].flux += capacitateMinima;
            matriceAdiacenta[curent][anterior].flux -= capacitateMinima;
        }

        fluxMaxim += capacitateMinima;
    }

    return fluxMaxim;
}

const vector<vector<Arc>>& Graf::getMatriceAdiacenta() const {
    return matriceAdiacenta;
}

int main() {
    int n;
    intrare >> n;

    Graf graf(2 * n + 2);

    for (int i = 0; i < n; ++i) {
        int x, y;
        intrare >> x >> y;
        graf.adaugaArc(2 * n, i, x);
        graf.adaugaArc(n + i, 2 * n + 1, y);

        for (int j = 0; j < n; ++j) {
            if (i != j) {
                graf.adaugaArc(i, n + j, 1);
            }
        }
    }

    int fluxMaxim = graf.fluxMaxim(2 * n, 2 * n + 1);

    iesire << fluxMaxim << endl;

    const vector<vector<Arc>>& matriceRezultat = graf.getMatriceAdiacenta();

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (matriceRezultat[i][n + j].flux == 1) {
                iesire << i + 1 << ' ' << j + 1 << endl;
            }
        }
    }

    return 0;
}