Cod sursa(job #2962196)

Utilizator gizzehhhAsavoaei Bianca Gabriela gizzehhh Data 7 ianuarie 2023 22:34:21
Problema Taramul Nicaieri Scor 30
Compilator cpp-64 Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I, Semestrul 2 Marime 2.52 kb
#include <fstream>
#include <queue>
#include <cmath>
#include <vector>

#define N 250 /// 2 * n + 1 e maxim
using namespace std;

ifstream fin("harta.in");
ofstream fout("harta.out");

int flux[N][N], out, in;
vector <int> tata;
vector <int> viz;
int n, m;
queue<int> c;

int S, T;
int sol_flux;

void Citire()
{
    fin >> n; /// nr de noduri
    S = 0;
    T = 2*n + 1;

    /// pt fiecare nod ni se spune cate muchii pleaca si intra
    for(int i = 1; i <= n; i++)
    {
        fin >> out >> in;

        /// dublam nodurile ca sa legam fiecare cu fiecare
        flux[S][i] = out;
        flux[n+i][T] = in;

        for(int j = 1; j <= n; j++)
            if( i != j)
               flux[i][n+j] = 1;
    }

}

int Constr_Lant_Nesat_BF()
{
    int vecin;
    tata.clear();
    tata.resize(T+1, 0);
    viz.clear();
    viz.resize(T+1, 0);

    c.push(S);
    viz[S] = 1;
    tata[S] = -1;
    int nod;
    while(c.empty() == 0)
    {

        nod = c.front();
        c.pop();
        if(nod == T)
            return 1;

        for(int i = 1; i <= T; i++)
            if( flux[nod][i] > 0 && viz[i] == 0)
        {
            c.push(i);
            viz[i] = 1;
            tata[i] = nod;
        }


    }

    return 0;
}

void Reviz_Flux_Lant()
{
    /// plecam in sens invers, de la T -> S

    for(int i=1; i<=n; i++)
        if(flux[n+i][T] > 0 && viz[n+i] == 1)
    {

        tata[T] = n + i;
        int flux_min = N*N;

        int nod = T;
        while(nod != S) /// cat timp nodul actual nu e nodul de unde am inceput
        {
            int parent = tata[nod];
            flux_min = min(flux_min, flux[parent][nod]);
            nod = parent;
        }

        if (flux_min == 0) continue;

        nod = T;
        while(nod != S)
        {
            int parent = tata[nod];
            flux[parent][nod] = flux[parent][nod] - flux_min;
            flux[nod][parent] = flux[nod][parent] + flux_min;

            nod = parent;

        }

        sol_flux = sol_flux + flux_min;
    }

}

void Implementare()
{
    while(Constr_Lant_Nesat_BF())
          Reviz_Flux_Lant();



    fout << sol_flux <<"\n";
    for(int i = 1; i<=n; i++)
        for(int j = 1; j<=n; j++)
            if(i!=j && flux[i][n+j] == 0)
                fout << i <<" "<< j <<"\n";
}

int main()
{
    Citire();
    Implementare();
   /* Reviz_Flux_Lant();
    fout << Constr_Lant_Nesat_BF() <<"\n";
    fout << sol_flux;*/
    return 0;
}