Cod sursa(job #3190117)

Utilizator AnaRosuAna Maria Rosu AnaRosu Data 6 ianuarie 2024 23:57:34
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream f("harta.in");
ofstream g("harta.out");

int n, m, s, t, pleaca, ajung, capac[202][202], flux[202][202];
vector<int> graf[202];

void constr_graf(){
    s = 0, t = n * 2 + 1;
    for(int nod = 1; nod <= n; nod++){
        f >> pleaca >> ajung;
        m += pleaca;

        capac[s][nod] = pleaca;
        capac[n + nod][t] = ajung;

        graf[s].push_back(nod);
        graf[n + nod].push_back(t);

        for(int copie = n; copie <= n * 2; copie++){
            if(copie - n != nod){
                capac[nod][copie] = 1;
                graf[nod].push_back(copie);
                graf[copie].push_back(nod);
            }
        }
    }
    f.close();
}

bool constr_drum_crestere(queue<int>& coada, vector<int>& tati, vector<int>& viz){
    coada.push(s);
    viz[s] = 1;
    while(!coada.empty()){
        int nod = coada.front();
        coada.pop();
        for (auto vecin : graf[nod])
            // lant nesaturat
            if(!viz[vecin] && capac[nod][vecin] - flux[nod][vecin] > 0){
                coada.push(vecin);
                tati[vecin] = nod;
                viz[vecin] = 1;

                if(vecin == t)
                    return true;
            }
    }
    return false;
}

void reviz_drum(queue<int>& coada, vector<int>& tati, vector<int>& viz){
    int fmax = 1;
    // cresc fluxul pe fiecare arc direct din drumul de crestere 
    // scad fluxul pe fiecare arc invers din drumul de crestere 
    int nod = t;
    while(nod != s){
        int prev = tati[nod];
        
        flux[prev][nod] += fmax;
        flux[nod][prev] -= fmax;

        nod = prev;
    }
}
void edmonds_karp(){
    queue<int> coada;
    vector<int> tati(202, -1);
    vector<int> viz(202, 0);
    while(constr_drum_crestere(coada, tati, viz)){
        reviz_drum(coada, tati, viz);
        coada = queue<int>();
        tati = vector<int>(202, -1);
        viz = vector<int>(202, 0);
    }
}

int main(){
    f >> n;
    constr_graf();
    edmonds_karp();
    g << m << endl;

    //parcurgem graful si vedem ce muchii 
    for(int nod = 1; nod <= n; nod++)
        for(int copie = n; copie <= n*2; copie++)
            if(flux[nod][copie])
                g << nod << " " << copie - n << endl;
    g.close();
    return 0;
}