Cod sursa(job #2961057)

Utilizator Rincu_StefaniaRincu Stefania Rincu_Stefania Data 5 ianuarie 2023 17:52:26
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.89 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
int tata[202] = {0}, viz[202] = {0};
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;
    in>>n;
    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;
            }
    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
    out<<edmonds_karp()<<"\n";

    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;
}