Maximal Flow (MPmag) 2023

// ConsoleApplication1.cpp : Этот файл содержит функцию "main". Здесь начинается и заканчивается выполнение программы.
//

#include <iostream>
#include <vector>
#include <queue>
#include <fstream>

using std::vector;
struct edge
{
    int beg, end;
    double c, f;
};
using wgraph = vector<vector<edge>>;
using edge_graph = vector<vector<std::pair<int, bool>>>;

wgraph get_wgraph_from_stream(std::istream& inp)
{
    int n;
    inp >> n;
    wgraph g(n);
    int beg, end;
    double c;
    while (inp >> beg >> end >> c)
    {
        g[beg].push_back({beg,end,c,0.0});
    }
    return g;
}

bool search_and_icrease_with_augment_path(const edge_graph& eg, vector<edge> &edges, int s, int t)
{
    int n = eg.size();
    vector<double> h(n,0);
    vector<int> p(n, -1);
    std::queue<int> Q;
    h[s] = DBL_MAX;
    Q.push(s);
    while (Q.size())
    {
        int u = Q.front();
        Q.pop();
        for (auto [en, out_edge] : eg[u])
        {
            if (out_edge && h[edges[en].end] == 0 && edges[en].c - edges[en].f > 0)
            {
                h[edges[en].end] = std::min(edges[en].c - edges[en].f,h[u]);
                p[edges[en].end] = en;
                Q.push(edges[en].end);
            }
            else if (!out_edge && h[edges[en].beg] == 0 && edges[en].f > 0)
            {
                h[edges[en].beg] = std::min(edges[en].f, h[u]);
                p[edges[en].beg] = en;
                Q.push(edges[en].beg);
            }
        }
        if (h[t] > 0) break;
    }
    if (h[t] == 0) return false;
    int current_edge = p[t], current_vertex=t;
    while (current_edge >= 0)
    {
        if (current_vertex == edges[current_edge].end)
        {
            edges[current_edge].f += h[t];
            current_vertex = edges[current_edge].beg;
        }
        else
        {
            edges[current_edge].f -= h[t];
            current_vertex = edges[current_edge].end;
        }
        current_edge = p[current_vertex];
    }
    return true;
}

vector<edge> maximal_flow(const wgraph& g, int s, int t)
{
    vector<edge> edges;

    edge_graph eg(g.size());
    //edge_graph[i] содержит список рёбер, инцидентных вершине i, а также признак исходящего ребра
    for (size_t u = 0; u < g.size(); u++)
    {
        for (auto [beg, end, c, f] : g[u])
        {
            edges.push_back({ beg,end,c,f });
            eg[beg].push_back({ edges.size() - 1, true });
            eg[end].push_back({ edges.size() - 1, false });
        }
    }
    while (search_and_icrease_with_augment_path(eg, edges, s, t)) { std::cout << '+'; }
    return edges;
}

int main()
{
    std::fstream inp("wgraph.txt");
    auto wg = get_wgraph_from_stream(inp);
    auto edges = maximal_flow(wg, 0, 3);
    for (auto e : edges)
    {
        std::cout << e.beg << " " << e.end << " " << e.c << " " << e.f << std::endl;
    }
    std::cout << "Hello World!\n";
}

// Запуск программы: CTRL+F5 или меню "Отладка" > "Запуск без отладки"
// Отладка программы: F5 или меню "Отладка" > "Запустить отладку"

// Советы по началу работы
//   1. В окне обозревателя решений можно добавлять файлы и управлять ими.
//   2. В окне Team Explorer можно подключиться к системе управления версиями.
//   3. В окне "Выходные данные" можно просматривать выходные данные сборки и другие сообщения.
//   4. В окне "Список ошибок" можно просматривать ошибки.
//   5. Последовательно выберите пункты меню "Проект" > "Добавить новый элемент", чтобы создать файлы кода, или "Проект" > "Добавить существующий элемент", чтобы добавить в проект существующие файлы кода.
//   6. Чтобы снова открыть этот проект позже, выберите пункты меню "Файл" > "Открыть" > "Проект" и выберите SLN-файл.