Cod sursa(job #3189831)

Utilizator dianam2003Manolache Diana Elena dianam2003 Data 6 ianuarie 2024 16:06:10
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.27 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

const int NR_MAX_NODURI = 301;

int grafFlux[NR_MAX_NODURI][NR_MAX_NODURI], parintiNoduri[NR_MAX_NODURI];
bool nodVizitat[NR_MAX_NODURI];

//citire
void citesteGraf(int& numarNoduri)
{
    fin >> numarNoduri;
    int muchiiOut, muchiiIn;
    for (int i = 1; i <= numarNoduri; i++)
    {
        fin >> muchiiOut >> muchiiIn;
        grafFlux[0][i] = muchiiOut;
        grafFlux[i + numarNoduri][numarNoduri * 2 + 1] = muchiiIn;
    }

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

//BFS
bool parcurgereBFS(int numarNoduri)
{
    queue<int> coada;
    for (int i = 0; i <= numarNoduri; i++)
    {
        nodVizitat[i] = false;
        parintiNoduri[i] = -1;
    }

    coada.push(0);
    nodVizitat[0] = true;

    while (!coada.empty())
    {
        int nodCurent = coada.front();
        coada.pop();
        for (int i = 0; i <= numarNoduri; i++)
        {
            if (grafFlux[nodCurent][i] > 0 && !nodVizitat[i])
            {
                coada.push(i);
                nodVizitat[i] = true;
                parintiNoduri[i] = nodCurent;
                if (i == numarNoduri)
                    return true;
            }
        }
    }

    return false;
}

//flux maxim in graf
int calculeazaFluxMaxim(int numarNoduri)
{
    int valoareFluxMaxim = 0;
    while (parcurgereBFS(numarNoduri))
    {
        for (int nodCurent = 1; nodCurent < numarNoduri; nodCurent++)
        {
            if (grafFlux[nodCurent][numarNoduri] > 0 && nodVizitat[nodCurent])
            {
                int nodPenultim = nodCurent;

                //construim calea curenta
                vector<int> caleCurenta;
                caleCurenta.push_back(numarNoduri);
                caleCurenta.push_back(nodPenultim);

                //parintele penultimului
                int nodParinte = parintiNoduri[nodPenultim];
                while (nodParinte != -1)
                {
                    caleCurenta.push_back(nodParinte);
                    nodParinte = parintiNoduri[nodParinte];
                }

                //capacitatea minima
                int bottleneck = 2;
                for (int i = 1; i < caleCurenta.size(); i++)
                    bottleneck = min(bottleneck, grafFlux[caleCurenta[i]][caleCurenta[i - 1]]);

                //actualizam fluxul maxim
                valoareFluxMaxim += bottleneck;
                for (int i = 1; i < caleCurenta.size(); i++) //si matricea de fluxuri
                {
                    grafFlux[caleCurenta[i]][caleCurenta[i - 1]] -= bottleneck;
                    grafFlux[caleCurenta[i - 1]][caleCurenta[i]] += bottleneck;
                }
            }
        }
    }
    return valoareFluxMaxim;
}

//afisare
void scrieRezultate(int numarNoduri)
{
    fout << calculeazaFluxMaxim(2 * numarNoduri + 1) << "\n";
    for (int i = 1; i <= numarNoduri; i++)
        for (int j = numarNoduri + 1; j <= numarNoduri * 2; j++)
            if (grafFlux[j][i] != 0)
                fout << i << " " << j - numarNoduri << "\n";
}

int main()
{
    int numarNoduri;
    citesteGraf(numarNoduri);
    scrieRezultate(numarNoduri);
    return 0;
}