Cod sursa(job #2961210)

Utilizator ioanatcioana t ioanatc Data 5 ianuarie 2023 23:28:14
Problema Taramul Nicaieri Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.76 kb
#include<iostream>
#include<fstream>
#include<queue>
using namespace std;
#define Max 1000

int N, x, y, maxflow, sum;

int graf_rez[Max][Max];
bool vizitat[Max];
int tata[Max];

void citesteDate();
void scrieRezultat();

bool lantBFS(){
    // initializare date
    for(int i = 0; i <= 2*N+1; i++){
        vizitat[i] = 0, tata[i] = -1;
    }

    queue<int> coada;
    coada.push(0); // nodul de start
    vizitat[0] = 1;

    while(!coada.empty()){
        int curent = coada.front();
        coada.pop();
        vizitat[curent] = 1;

        if(curent == 2*N+1) return true;

        for(int nod = 1; nod <= 2*N+1; nod ++){
            if(!vizitat[nod] && graf_rez[curent][nod] > 0){

                tata[nod] = curent;
                coada.push(nod);
            }
        }
    }
    return false;
}
int main(){
    citesteDate();

    // cat timp se poate construi un lant minim
    while(lantBFS()){

        // pornim verificarea tuturor lanturilor gasite de la nodurile tata ale nodului final
        for(int nod = 1; nod <= 2*N; nod ++){
            if(vizitat[nod] && graf_rez[nod][2*N+1] > 0) // valoare pozitiva => muchia nu este saturata
            {
                // aflam valoarea minima a fluxului in cadrul lantului curent
                int flux_curent = graf_rez[nod][2*N+1];
                // actualizam tatal nodului final in functie de lantul curent gasit
                tata[2*N+1] = nod;

                int auxiliar = nod;
                while(tata[auxiliar] != -1){
                    flux_curent = min(flux_curent, graf_rez[tata[auxiliar]][auxiliar]);
                    auxiliar = tata[auxiliar];
                }
                if(flux_curent > 0){

                    auxiliar = 2*N+1;
                    while(tata[auxiliar] != -1){
                        graf_rez[ tata[auxiliar] ][ auxiliar ] -= flux_curent;
                        graf_rez[ auxiliar ][ tata[auxiliar] ] += flux_curent;
                        auxiliar = tata[auxiliar];
                    }
                    // actualizam fluxul maxim
                    maxflow += flux_curent;
                }
            }
        }
    }

    scrieRezultat();
    return 0;
}
void citesteDate(){
    ifstream f("harta.in");

    f>>N;
    for(int i=1; i<=N; i++){
        f>>x>>y;
        graf_rez[0][i] = x;
        graf_rez[N+i][2*N+1] = y;
    }
    // initializare date
    for(int i=1; i<=N; i++)
        for(int j=1; j<=N; j++)
            if(j!=i)
                graf_rez[i][N+j] = 1;
}
void scrieRezultat(){
    ofstream g("harta.out");

    g<<maxflow<<"\n";
    for(int i=1; i<=N; i++)
        for(int j=1; j<=N; j++)
            if(i != j && graf_rez[N+j][i])
                g<<i<<" "<<j<<"\n";
}