Cod sursa(job #3186835)

Utilizator TL_2022T123 L456 TL_2022 Data 25 decembrie 2023 20:44:21
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.75 kb
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <climits>

class graf_flux
{
    int n;
    std::vector<std::vector<int>>& adj_list;
    std::vector<std::vector<int>> adj_list_rev;
    std::vector<std::vector<int>>& capacitati;
    std::vector<std::vector<int>> flux;
    int sursa;
    int destinatie;
    std::vector<int> tata;
public:
    graf_flux(int n_, std::vector<std::vector<int>>& adj_list_,
               std::vector<std::vector<int>>& capacitati_, int sursa_, int destinatie_);
    const std::vector<int>& get_tata()const;
    bool construieste_lant_nesaturat();
    int flux_muchie(int x, int y) const;
    void update_flux();

    void print_cap()const{
        std::cout<<"\n-------------------------\n";
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
                std::cout<<capacitati[i][j]<<" ";
            std::cout<<"\n";
        }
        std::cout<<"-------------------------\n";
    }
    void print_flux()const{
        std::cout<<"\n-------------------------\n";
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
                std::cout<<flux[i][j]<<" ";
            std::cout<<"\n";
        }
        std::cout<<"-------------------------\n";
    }
};

int main()
{
    std::ifstream f("harta.in");
    std::ofstream h("harta.out");

    int n = 0;
    f >> n;
    int din = 0;
    int dout = 0;
    std::vector<std::vector<int>> adj_list(2*n+2);
    std::vector<std::vector<int>> cap(2*n + 2, std::vector<int>(2*n + 2, 1));
    for(int i=0;i<2*n + 2;i++)
        cap[i][i]=0;

    for(int i=1;i<=n;i++)
        for(int j=n+1;j<=2*n;j++)
            if(i!=j)
                adj_list.at(i).push_back(j);

    for(int i=1;i<=n;i++)
    {
        f >> dout >> din;
        adj_list[0].push_back(i);
        adj_list[i+n].push_back(2*n + 1);
        cap[0][i] = din;
        cap[i+n][2*n + 1] = dout;
    }

    graf_flux g(2*n + 2, adj_list, cap,0, 2*n + 1);

    int flux = 0;
    std::vector<std::vector<int>> muchii;

    while(g.construieste_lant_nesaturat())
    {
        g.update_flux();
        auto tata = g.get_tata();
        int node = 2*n + 1;
        int y = tata[node];
        int x = tata[y];
        flux += g.flux_muchie(x,y);
        muchii.push_back(std::vector<int>{x, y-n});
    }

    h << flux << "\n";
    for(auto i: muchii)
        h << i[0] << " " << i[1] << "\n";

    f.close();
    h.close();
    return 0;
}


graf_flux::graf_flux(int n_, std::vector<std::vector<int>>& adj_list_, std::vector<std::vector<int>>& capacitati_,
                      int sursa_, int destinatie_): n(n_), adj_list(adj_list_), capacitati(capacitati_), sursa(sursa_), destinatie(destinatie_)
{
    flux = std::vector<std::vector<int>>(n, std::vector<int>(n, 0));

    adj_list_rev = std::vector<std::vector<int>>(n);
    for(int i=0; i<n; ++i)
        for(auto j: adj_list[i])
        adj_list_rev[j].push_back(i);
}

const std::vector<int>& graf_flux::get_tata()const
{
    return tata;
}

bool graf_flux::construieste_lant_nesaturat()
{
    std::vector<bool> viz(n, false);
    tata = std::vector<int>(n, INT_MAX);
    std::queue<int> q;
    q.push(sursa);
    viz[sursa] = true;
    tata[sursa] = sursa;
    while(!q.empty())
    {
//        std::cout<<1;
        int node = q.front();
        q.pop();
        for(auto vec: adj_list[node])
            if(!viz[vec] && capacitati[node][vec] - flux[node][vec] > 0)
            {
                q.push(vec);
//                std::cout<<"pushed "<<vec<<"\n";
                tata[vec] = node;
                viz[vec] = true;
                if(vec == destinatie) return true;
            }
        for(auto vec: adj_list_rev[node])
            if(!viz[vec] && flux[vec][node] > 0)
            {
                q.push(vec);
                tata[vec] = -node;
                viz[vec] = true;
                if(vec == destinatie) return true;
            }
    }
//    std::cout<<"niciun drum de crestere!!!\n";
    return false;
}

int graf_flux::flux_muchie(int x, int y) const
{
    return flux[x][y];
}

void graf_flux::update_flux()
{
    int node = destinatie;
    int f_min = INT_MAX;

    for(int i=0;i<n;i++)

    while(tata[node] != node)
    {
        if(tata[node] < 0)
            f_min = std::min(f_min, flux[-tata[node]][node]);
        else
            f_min = std::min(f_min, capacitati[tata[node]][node] - flux[tata[node]][node]);
        node = tata[node];
    }
    node = destinatie;
    while(tata[node] != node)
    {
        if(tata[node] < 0)
            flux[-tata[node]][node] -= f_min;
        else
            flux[tata[node]][node] += f_min;
        node = tata[node];
    }
}