Cod sursa(job #3188874)

Utilizator Cosmin.BoeriuCosmin Boeriu George Cosmin.Boeriu Data 3 ianuarie 2024 22:38:26
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream fin("harta.in");
ofstream fout("harta.out");
//sursa = 0; nodurile_out = 1..n, nodurile_in = n+1..2n, dest = ultimu(2n+1);
int capacitate[204][204], n, suma_oprire;
vector<vector<int>> adj(100);

int drum_crestere(vector<int>&parent){
    parent = vector<int>(2*n+2, -1);
    queue<int>q;
    int nod_curent;
    q.push(0);
    while(!q.empty()){
        nod_curent = q.front();
        q.pop();
        for(int i = 2*n+1; i > 0; i--){
            if(parent[i] == -1 && capacitate[nod_curent][i] > 0){
                parent[i] = nod_curent;
                if(i == 2*n+1){
                    return 1;
                }
                q.push(i);
            }
        }
    }
    return 0;
}

void fluxmax(){
    int flux = 0;
    vector<int>parent(2*n+1);
    while(flux != suma_oprire){
        flux += drum_crestere(parent);
        int curent = 2*n+1, precedent;
        while(curent != 0){
            precedent = parent[curent];    // Cum ar veni
            capacitate[precedent][curent] -= 1; // din prev am dat una catre curent si fluxu e mai mic
            capacitate[curent][precedent] += 1; // si acum curent poate intoarce cu 1 mai mult in prev
            curent = precedent;
        }
    }
}

int main()
{
    int i, j;

    fin>>n;
    for(i = 1; i <= n; i++){
        fin>>capacitate[0][i]>>capacitate[n+i][2*n+1];
        suma_oprire += capacitate[0][i];
    }
    for(i = 1; i <= n; i++){
        for(j = n+1; j <= 2*n; j++){
            if(i != j - n){
                capacitate[i][j] = 1;
            }
        }
    }

    fluxmax();
    fout<<suma_oprire<<'\n';
    for(i = n+1; i <= 2*n; i++){
        for(j = 1; j <= n; j++){
            if(capacitate[i][j] == 1){
                fout<<j<<' '<<i-n<<'\n';
            }
        }
    }
    return 0;
}