Cod sursa(job #3189382)

Utilizator IustinSoadMitu Iustin IustinSoad Data 5 ianuarie 2024 01:15:11
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.95 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream input("harta.in");
ofstream output("harta.out");

const int MAX_N = 202;

int nod_sursa, nod_destinatie;

vector<vector<int>> flux(MAX_N, vector<int>(MAX_N, 0));
vector<vector<int>> capacitate(MAX_N, vector<int>(MAX_N, 0));
vector<int> flux_temporar(MAX_N, 0);

// vector de tati
vector<int> parinti(MAX_N, -1);

// matricea de adiacenta
vector<vector<int>> vecini(MAX_N);

queue<int> coada_bfs;

/*
    Aceasta functie cauta efectiv path uri
adiacente care pot imbunatati flow ul.
*/
int BFS() {
    fill(parinti.begin(), parinti.end(), -1);
    parinti[nod_sursa] = 0;
    fill(flux_temporar.begin(), flux_temporar.end(), 0);

    while (!coada_bfs.empty()) coada_bfs.pop();
    coada_bfs.push(nod_sursa);
    flux_temporar[nod_sursa] = 10000;

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

        for (int vecin : vecini[curent]) {
            if (parinti[vecin] == -1 && capacitate[curent][vecin] - flux[curent][vecin] > 0) {
                parinti[vecin] = curent;
                flux_temporar[vecin] = min(flux_temporar[curent], (capacitate[curent][vecin] - flux[curent][vecin]));

                if (vecin == nod_destinatie)
                    return flux_temporar[nod_destinatie];

                coada_bfs.push(vecin);
            }
        }
    }

    return 0;
}

int main() {
    int num_orase;
    input >> num_orase;
    nod_destinatie = 2 * num_orase + 1;

    // aici creem flow ul initial 

    for (int i = 1; i <= num_orase; i++) {
        int iesire, intrare;
        input >> iesire >> intrare;

        capacitate[nod_sursa][i] = iesire;
        capacitate[i + num_orase][nod_destinatie] = intrare;

        vecini[nod_sursa].push_back(i);
        vecini[num_orase + i].push_back(nod_destinatie);

        for (int j = num_orase + 1; j <= num_orase * 2; j++) {
            if (j != i + num_orase) {
                capacitate[i][j] = 1;
                vecini[i].push_back(j);
                vecini[j].push_back(i);
            }
        }
    }

    int flux_maxim = 0;

    fill(flux.begin(), flux.end(), vector<int>(MAX_N, 0));

    // Ford-Fulkerson
    while (true) {
        int flux_curent = BFS();

        if (flux_curent == 0)
            break;

        flux_maxim += flux_curent;

        int nod_curent = nod_destinatie;

        while (nod_curent != nod_sursa) {
            flux[parinti[nod_curent]][nod_curent] += flux_curent;
            flux[nod_curent][parinti[nod_curent]] -= flux_curent;
            nod_curent = parinti[nod_curent];
        }
    }

    output << flux_maxim << endl;

    for (int i = 1; i <= num_orase; i++)
        for (int j = 1 + num_orase; j <= num_orase * 2; j++)
            if (flux[i][j])
                output << i << ' ' << j - num_orase << endl;

    return 0;
}