Cod sursa(job #2962159)

Utilizator MoarcascosminMoarcas Cosmin Moarcascosmin Data 7 ianuarie 2023 21:23:39
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.65 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <queue>

using namespace std;

int n, numarNoduri, numarDrumuri;

int sursa, destinatie;

int capacitate[201][201];
int flux[201][201];
bool vizitat[201];
int tata[201];

vector<vector<int>> vecini;

void Citire()
{
    ifstream f("harta.in");

    int numarIntrari, numarIesiri;

    f >> n;

    /**
     * - n noduri pentru muchiile de intrare (legate de nodul de sursa)
     * - n noduri pentru muchiile de iesire (legate de nodul final)
     * - un nod de sursa si un nod de final
     * 
     * Am noduri de la 0 la numarNoduri - 1
    */
    numarNoduri = 2 * n + 2; 
    sursa = 0;
    destinatie = numarNoduri - 1;

    vecini.resize(numarNoduri);

    // Creez matricea capacitate
    for(int nod = 1; nod <= n; nod++)
    {
        f >> numarIntrari >> numarIesiri;

        capacitate[sursa][nod] = numarIntrari;
        capacitate[nod + n][destinatie] = numarIesiri;
    }
}

void FormareMuchii()
{
    // Formez muchiile de la sursa la nodurule 1 .. n
    for(int nod = 1; nod <= n; nod++)
    {
        vecini[sursa].push_back(nod);
        vecini[nod].push_back(sursa);
    }

    // Formez muchiile de la nodurile (n + 1) .. (2 * n + 1) la nodul destinatie
    for(int nod = n + 1; nod < numarNoduri - 1; nod++)
    {
        vecini[nod].push_back(destinatie);
        vecini[destinatie].push_back(nod);
    } 

    // Formez muchiile intre nodurile 1 .. n si nodurile (n + 1) .. (2 * n + 1)
    for(int nod = 1; nod <= n; nod++)
        for(int nodVecin = n + 1; nodVecin < numarNoduri - 1; nodVecin++)
        {
            if(nodVecin - nod == n)
                continue;

            vecini[nod].push_back(nodVecin);
            vecini[nodVecin].push_back(nod);

            // Setez capacitatea pe 1
            capacitate[nod][nodVecin] = 1;
        }
}

void ResetareVizitat()
{
    for(int nod = 0; nod < numarNoduri; nod++)
    {
        vizitat[nod] = false;
    }
}

int Bfs()
{
    queue<int> coada;

    ResetareVizitat();

    vizitat[sursa] = true;
    coada.push(sursa);

    while(!coada.empty())
    {
        int nodCurent = coada.front();
        coada.pop();
        for(auto nodVecin : vecini[nodCurent])
        {
            if(!vizitat[nodVecin] && flux[nodCurent][nodVecin] < capacitate[nodCurent][nodVecin])
            {
                vizitat[nodVecin] = true;                
                tata[nodVecin] = nodCurent;
                coada.push(nodVecin);

                if(nodVecin == destinatie)
                    return 1;
            }
        }
    }
    return 0;
}

void ActualizareFlux(int nod)
{
    if(nod == sursa)
        return;

    int nodTata = tata[nod];

    flux[nodTata][nod] += 1;
    flux[nod][nodTata] -= 1;

    ActualizareFlux(nodTata);
}

int FluxRamasMinim(int nod)
{
    if(nod == sursa)
        return 1000000000;
    
    int nodTata = tata[nod];

    int fluxRamas = capacitate[nodTata][nod] - flux[nodTata][nod];

    return min(fluxRamas, FluxRamasMinim(nodTata));    
}

void DeterminareSolutie()
{
    while(Bfs())
    {
        for(auto nodVecin : vecini[destinatie])
        {
            if(!vizitat[nodVecin] || FluxRamasMinim(destinatie) == 0) 
                continue;

            numarDrumuri++;

            ActualizareFlux(destinatie);
        }
    }
}

void Afisare()
{
    ofstream g("harta.out");

    g << numarDrumuri << endl;

    for(int nod = 1; nod <= n; nod++)
        for(int nodVecin = n + 1; nodVecin < numarNoduri; nodVecin++)
        {
            if(flux[nod][nodVecin] == 1)
                g << nod << " " << nodVecin - n << endl;
        }
}

int main()
{
    Citire();
    FormareMuchii();
    DeterminareSolutie();
    Afisare();
    return 0;
}