Cod sursa(job #2961061)

Utilizator Rincu_StefaniaRincu Stefania Rincu_Stefania Data 5 ianuarie 2023 17:58:52
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.54 kb
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <fstream>

using namespace std;

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

///capacity -> capacitatea muchiei
int capacity[202][202];
///l -> vecorul care retine graful + graful rezidual
vector<int> l[2002];
///vectorul de parinti si cel de vizitate
int tata[202] = {0}, viz[202] = {0};
///nr de muchii
int n;

int bfs()
{
    queue<int> q;
    ///rescriem valorile din vectorul de tati si cel de vizitate
    memset(tata, 0, sizeof(tata));
    memset(viz, 0, sizeof(viz));

    q.push(0);
    viz[0] = 1;
    tata[0] = -1;

    ///BFS clasic
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        ///iesim cu 1 daca am ajuns la nodul 2*n+1
        if(u == 2*n+1)
            return 1;
        for(int i = 0; i < l[u].size(); i++)
        {
            int v = l[u][i];
            ///inseamna ca nu e vizitat
            if(capacity[u][v] > 0 && !viz[v])
            {
                ///updatam vectorul de tati pentru a avea drumul
                tata[v] = u;
                ///setam nodul ca vizitat
                viz[v] = 1;
                q.push(v);
            }
        }
    }
    return 0;
}

///pentru a optimiza programul efectuam algoritmul lui Edmonds Karp atata timp
///cat prin parcurerea BFS putem ajunge din nodul 1 in nodul n, ceea ce inseamna
///ca estista un drum pe care fluxul rezidual sa fie minim si mai am capacitate
///disponibila pe muchii pentru a mari fluxul
int edmonds_karp()
{
    ///maxim -> fluxul maxim, minim -> fluxul minim rezidual gasit dupa parcurgerea BFS
    ///u -> nodul curent, v -> vecinul acestuia
    int maxim = 0, minim, u, v;
    ///cat timp prin parcurgerea BFS ajung din nodul 1 in nodul n
    while(bfs())
    {
        ///iterez prin vecinii nodului n(final)
        for(int i = 0; i < l[2*n+1].size(); i++)
        {
            u = l[2*n+1][i];
            ///daca mai am capacitate disponibila pe muchia dintre noduri
            ///si nodul e vizitat atunci calculam fluxul minim rezidual
            if(capacity[u][2*n+1] > 0 && viz[u])
            {
                ///in BFS am pastrat in vectorul de tati drumul gasit pentru transmiterea fluxului
                ///iar acum parcurgem acel drum pentru a gasi minimul si pentru a reactualiza capacitatile
                ///de pe muchii, in functie de cum apar in parcurgere

                minim = capacity[u][2*n+1];
                while(tata[u] != -1)
                {
                    v = tata[u];
                    minim = min(minim, capacity[v][u]);
                    u = v;
                }
                maxim += minim;
                u = l[2*n+1][i];
                capacity[u][2*n+1] -= minim;
                capacity[2*n+1][u] += minim;
                while(tata[u] != -1)
                {
                    v = tata[u];
                    capacity[v][u] -= minim;
                    capacity[u][v] += minim;
                    u = v;
                }
            }
        }
    }
    return maxim;
}

int main()
{
    int di, de;
    ///citim nr de muchii date
    in>>n;
    ///cream un graf complet de n noduri cu ajutorul caruia avem in stanga nodurile propriu zise si in dreapta copiile lor
    ///adaugam capacitatea 1 pe muchia dintre ele
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(i != j)
            {
                l[i].push_back(j+n);
                l[j+n].push_back(i);
                capacity[i][j+n] = 1;
            }
    ///citim gradele date si pentru fiecare pereche data, pentru gradele de intrare legam de un nod fictiv (-> 0) nodul curent
    ///si adaugam costul nr.gradelor de intrare, iar pt gradele de iesire legam fiecare nod clona din partea stanga de un nod fictiv
    ///(-> 2*n+1) si adaugam costul dintre ele nr gradelor de iesire
    for(int i = 1; i <= n; i++)
    {
        in>>di>>de;
        l[0].push_back(i);
        l[i].push_back(0);
        capacity[0][i] = di;
        l[2*n+1].push_back(i+n);
        l[i+n].push_back(2*n+1);
        capacity[i+n][2*n+1] = de;
    }

    ///calculam fluxul maxim cu ajutorul algoritmului Edmonds Karp, ceea ce va determina nr de noduri
    out<<edmonds_karp()<<"\n";

    ///afisam perechile de noduri care au muchii intre ele
    for(int i = 1; i <= n; i++)
        for(int j = n+1; j <= 2*n; j++)
            if(capacity[j][i] == 1)
                out<<i<<" "<<j-n<<"\n";
    return 0;
}