11. Максимальный поток V (Форд-Фалкерсон)

bool DFS(string u, string t, map<string, bool>& visited, map<string, string>& parent, map<string, map<string, int>>& graf_res) {
        visited[u] = true;
        if (u == t) return true;

        for (const auto& neighbor : graf_res[u]) {
            string v = neighbor.first;
            int capacity = neighbor.second;

            if (!visited[v] && capacity > 0) {
                parent[v] = u;
                if (DFS(v, t, visited, parent, graf_res)) {
                    return true;
                }
            }
        }
        return false;
    }

    void FordFulkerson(string s, string t) {
        if (!ExistVertex(s) || !ExistVertex(t)) {
            cout << "Исток или сток не существует" << endl;
            return;
        }

        map<string, map<string, int>> graf_res = AdjList;
        map<string, string> parent;
        int maxFlow = 0;

        while (true) {
            map<string, bool> visited;
            parent.clear();

            // Поиск увеличивающего пути
            if (!DFS(s, t, visited, parent, graf_res)) break;

            // Определяем минимальный поток в найденном пути
            int pathFlow = INF;
            for (string v = t; v != s; v = parent[v]) {
                string u = parent[v];
                pathFlow = min(pathFlow, graf_res[u][v]);
            }

            // Обновляем резервный граф
            for (string v = t; v != s; v = parent[v]) {
                string u = parent[v];
                graf_res[u][v] -= pathFlow;
                graf_res[v][u] += pathFlow;
            }

            maxFlow += pathFlow;
        }

        cout << "Максимальный поток из " << s << " в " << t << ": " << maxFlow << endl;
    }


//main.cpp

#include <iostream>
#include <string>
#include <vector>
#include <fstream>
#include <vector>
#include <list>
#include <map>
#include <locale>
#include <windows.h>
#include "Graph.h"

using namespace std;

int main() {
    setlocale(LC_ALL, "Russian");
    SetConsoleOutputCP(CP_UTF8);

    cout << "Задание 11\n";
    Graph g1;
    g1.loadFromFile("potok.txt");

    string s, t;
    cout << "введите исток и сток: "; cin >> s >> t;
    g1.FordFulkerson(s, t);

}

//potok.txt
directed
weighted
s a 10
s b 10
b a 2
a c 4
a t 8
b t 9
c t 10