Cod sursa(job #2958530)

Utilizator mihairazvan03Dana Mihai mihairazvan03 Data 26 decembrie 2022 20:58:30
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.69 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>

//creem o matrice de adiacenta in care adaugam un nod initial, care pleaca spre toate celelalte noduri si unul final in care ajung toate celelalte noduri, iar apoi dublam nodurile. Intre fiecare
//2 noduri (inafara de cel initial si final) adaugam in aceasta 1 (deoarece avem un flux maxim de 1). Apoi facem ford fulkerson.
//Complexitate timp la ford fulkerson O(nm); n nr noduri, m nr muchii, iar in cazul nostru avem 2 * n + 2 noduri si n * n muchii deci complex este O(n^3), iar de spatiu O(n ^ 2)

using namespace std;
using namespace std;
ifstream in("harta.in");
ofstream out("harta.out");

int n, fluxMaxim;          //fluxMaxim va reprezenta aici nr de drumuri construite
vector<vector<int>> ramas;
vector<int> visited, dad;
queue<int> coada;

bool construiesteDrum()
{
    int i, nodCurent;

    while(!coada.empty())
        coada.pop();

    for(i = 0; i <= 2 * n + 1; i++)
    {
        dad[i] = -1;
        visited[i] = 0;
    }

    coada.push(0);         //pornim de la nodul 0 pt ca ala e nodul de start (nodul 0 fiind nodul de start creat de noi)
    visited[0] = 1;

    while(!coada.empty())
    {
        nodCurent = coada.front();
        coada.pop();

        if (nodCurent == 2 * n + 1)   //daca am ajuns la 2 * n + 1 care e destinatia inseamna ca am reusit sa creem un drum
            return true;

        for(i = 1; i <= 2 * n + 1; i++)   //parcurgem toate nodurile si vedem daca se poate ajunge din nodul curent in respectivul nod (adica sa nu fie vizitat si sa mai avem capacitate ramasa)
            if(ramas[nodCurent][i] > 0 && visited[i] == 0)
            {
                visited[i] = 1;
                dad[i] = nodCurent;
                coada.push(i);
            }
    }

    return false;  //daca se ajunge aici inseamna ca if(nodCurent == n) nu a fost apelat, deci nu s-a ajuns pana la destinatie, deci nu am reusit sa creem un drum
}

void calculeazaFluxMax()
{
    int i, fiu, nodCurent, j, bootleNeck;
    vector<int> drum;

    while(construiesteDrum())    //daca nu mai gasim un drum ne oprim
    {
        for(i = n + 1; i < 2 * n + 1; i++)   //incercam sa reconstruim drumurile
        {
            if(ramas[i][2 * n + 1] > 0 && visited[i] == 1)  //inseamna ca din nodul i la care suntem acuma s-a transportat o anumita cantitate in nodul final
            {
                fiu = i;
                drum.clear();      //daca nu facem asta ramane din forul anterior
                drum.push_back(2 * n + 1);
                drum.push_back(fiu);
                nodCurent = dad[fiu];

                while (nodCurent != 0)     //mergem inapoi pe traseu si reconstruim drumul
                {
                    drum.push_back(nodCurent);
                    nodCurent = dad[nodCurent];
                }

                drum.push_back(0);

                bootleNeck = INT_MAX;

                for(j = drum.size() - 1; j >= 1; j--)     //parcurgem pe invers pt ca noi in drum am pus elementele pornind de la destinatie spre start
                    bootleNeck = min(bootleNeck, ramas[drum[j]][drum[j - 1]]);

                fluxMaxim += bootleNeck;

                for(j = drum.size() - 1; j >= 1; j--)
                {
                    ramas[drum[j]][drum[j - 1]] -= bootleNeck;   //scadem capacitatea ramase pt drumurile prin care am trecut
                    ramas[drum[j - 1]][drum[j]] += bootleNeck;   //in cazul drumurilor reversed crestem aceasta capacitate
                }
            }
        }
    }
}

int main()
{
    int i, j, nrOut, nrIn;

    in >> n;

    dad.resize(2 * n + 2);
    visited.resize(2 * n + 2);
    ramas.resize(2 * n + 2);

    for(i = 0; i <= 2 * n + 1; i++)
        ramas[i].resize(2 * n + 2, 0);

    for(i = 1; i <= n; i++)
    {
        in >> nrOut >> nrIn;
        ramas[0][i] = nrOut;          //creem un nod de start, pt care pleaca catre fiecare nod o muchie cu capacitatea egala cu cate muchii pleaca din nodul respectiv mai departe
        ramas[n+i][2 * n + 1] = nrIn;       //creem un nod destinatie, in care intra pt fiecare nod o muchie cu capacitatea egala cu cate muchii intra in nodul respectiv

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

    calculeazaFluxMax();

    out << fluxMaxim << '\n';      //nr de drumuri construite

    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)
            if(i != j && ramas[i][n + j] == 0)      //inseamna ca am construit drum intre nodul i si j daca capacitatea ramasa e 0
               out << i << " " << j << '\n';

    return 0;
}