Алгоритм Форда-Фалкерсона: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
(не показано 10 промежуточных версий этого же участника)
Строка 1: Строка 1:
  #include <stdio.h>
  class Graph {
#include <algorithm>
    struct Edge {
#include <vector>
        int a, b, capacity, flow = 0;
using namespace std;
   
   
struct Edge {
        Edge(int a, int b, int capacity) :
    int a, b, cap, flow;
            a(a), b(b), capacity(capacity) {}
    Edge(int a, int b, int cap, int flow) : a(a), b(b), cap(cap), flow(flow) {}
};
        int other(int v) const {
  vector<Edge> edges;
            return v == a ? b : a;
        }
        int capacityTo(int v) const {
            return v == b ? capacity - flow : flow;
        }
        void addFlowTo(int v, int deltaFlow) {
            flow += (v == b ? deltaFlow : -deltaFlow);
        }
    };
   
    vector<Edge> edges;
    vector<vector<int>> graph;
    vector<bool> visited;
    vector<int> edgeTo;
   
   
int n, m, u[1010], INF = 1 << 30;
    void dfs(int v) {
vector<int> g[1010];
        visited[v] = 1;
        for (int e : graph[v]) {
            int to = edges[e].other(v);
            if (!visited[to] && edges[e].capacityTo(to)) {
                edgeTo[to] = e;
                dfs(to);
            }
        }
    }
   
   
int findPath(int v, int bottleneckFlow) {
    bool hasPath(int start, int finish) {
    u[v] = 1;
         visited.assign(visited.size(), 0);
    if (v == n - 1)
        dfs(start);
         return bottleneckFlow;
        return visited[finish];
    for (int i = 0; i < g[v].size(); i++) {
        Edge &e = edges[g[v][i]], &re = edges[g[v][i] ^ 1];
        if (!u[e.b] && e.cap > e.flow) {
            int deltaFlow = findPath(e.b, min(bottleneckFlow, e.cap - e.flow));
            if (deltaFlow) {
                e.flow += deltaFlow;
                re.flow -= deltaFlow;
                return deltaFlow;
            }
        }
     }
     }
    return 0;
}
   
   
int main() {
    int bottleneckCapacity(int start, int finish) {
    scanf("%d%d", &n, &m);
        int bCapacity = 1e9;
    int a, b, cap;
        for (int v = finish; v != start; v = edges[edgeTo[v]].other(v))
    for (int i = 0; i < m; i++) {
            bCapacity = min(bCapacity, edges[edgeTo[v]].capacityTo(v));
        scanf("%d%d%d", &a, &b, &cap);
         return bCapacity;
        edges.push_back(Edge(a - 1, b - 1, cap, 0));
        g[a - 1].push_back(edges.size() - 1);
        edges.push_back(Edge(b - 1, a - 1, cap, cap));
         g[b - 1].push_back(edges.size() - 1);
     }
     }
   
     int flow = 0;
     void addFlow(int start, int finish, int deltaFlow) {
    while (1) {
         for (int v = finish; v != start; v = edges[edgeTo[v]].other(v))
         fill(u, u + n, 0);
            edges[edgeTo[v]].addFlowTo(v, deltaFlow);
        int deltaFlow = findPath(0, INF);
        if (!deltaFlow)
            break;
        flow += deltaFlow;
     }
     }
    printf("%d", flow);
}
   
   
public:
    Graph(int vertexCount) :
        graph(vertexCount), visited(vertexCount), edgeTo(vertexCount) {}
       
    void addEdge(int from, int to, int capacity) {
        edges.push_back(Edge(from, to, capacity));
        graph[from].push_back(edges.size() - 1);
        graph[to].push_back(edges.size() - 1);
    }
    long long maxFlow(int start, int finish) {
        long long flow = 0;
        while (hasPath(start, finish)) {
            int deltaFlow = bottleneckCapacity(start, finish);
            addFlow(start, finish, deltaFlow);
            flow += deltaFlow;
        }
        return flow;
    }
};
== Ссылки ==
== Ссылки ==
* [http://algs4.cs.princeton.edu/lectures/64MaxFlow.pdf algs4.cs.princeton.edu/lectures &mdash; 6.4 Maximum Flow]
Теория:
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A4%D0%BE%D1%80%D0%B4%D0%B0-%D0%A4%D0%B0%D0%BB%D0%BA%D0%B5%D1%80%D1%81%D0%BE%D0%BD%D0%B0,_%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D1%81_%D0%BF%D0%BE%D0%BC%D0%BE%D1%89%D1%8C%D1%8E_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83 neerc.ifmo.ru/wiki &mdash; Алгоритм Форда-Фалкерсона]
* [https://algs4.cs.princeton.edu/lectures/keynote/64MaxFlow.pdf algs4.cs.princeton.edu 6.4 Maximum Flow]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A4%D0%BE%D1%80%D0%B4%D0%B0-%D0%A4%D0%B0%D0%BB%D0%BA%D0%B5%D1%80%D1%81%D0%BE%D0%BD%D0%B0,_%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D1%81_%D0%BF%D0%BE%D0%BC%D0%BE%D1%89%D1%8C%D1%8E_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83 neerc.ifmo.ru/wiki — Алгоритм Форда-Фалкерсона]
* [http://brilliant.org/wiki/ford-fulkerson-algorithm Brilliant.org — Ford-Fulkerson Algorithm]
Демонстрация:
* [https://visualgo.net/en/maxflow VisuAlgo — Network Flow]
Код:
* [https://github.com/indy256/codelibrary/blob/master/java/graphs/flows/MaxFlowFordFulkerson.java CodeLibrary — Maximum flow. Ford-Fulkerson alogithm in O(V^2 * FLOW)]
* [http://github.com/ADJA/algos/blob/master/Graphs/FordFulkerson.cpp Algos &mdash; Ford-Fulkerson maxflow]
* algs4.cs.princeton.edu/code &mdash; [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/FlowEdge.java.html capacitated edge with flow], [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/FlowNetwork.java.html capacitated network], [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/FordFulkerson.java.html maxflow–mincut] (несмотря на название, используется алгоритм Эдмондса-Карпа)
Задачи:
* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru &mdash; Курс &laquo;Алгоритмы на графах&raquo; &mdash; часть 9]
* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru &mdash; Курс &laquo;Алгоритмы на графах&raquo; &mdash; часть 9]
* [http://github.com/indy256/codelibrary/blob/master/java/src/MaxFlowFordFulkerson.java CodeLibrary &mdash; Maximum flow. Ford-Fulkerson alogithm in O(V^2 * FLOW)]
* [[:Категория:Задачи: Максимальный поток|Задачи: Максимальный поток]]
* [http://github.com/ADJA/algos/blob/master/Graphs/FordFulkerson.cpp Algos &mdash; Ford-Fulkerson maxflow]
 
* [http://visualgo.net/maxflow.html VisuAlgo &mdash; Network Flow]
[[Category: Максимальный поток]]

Текущая версия от 13:23, 1 июля 2023

class Graph {
    struct Edge {
        int a, b, capacity, flow = 0;

        Edge(int a, int b, int capacity) :
            a(a), b(b), capacity(capacity) {}

        int other(int v) const {
            return v == a ? b : a;
        }

        int capacityTo(int v) const {
            return v == b ? capacity - flow : flow;
        }

        void addFlowTo(int v, int deltaFlow) {
            flow += (v == b ? deltaFlow : -deltaFlow);
        }
    };

    vector<Edge> edges;
    vector<vector<int>> graph;
    vector<bool> visited;
    vector<int> edgeTo;

    void dfs(int v) {
        visited[v] = 1;
        for (int e : graph[v]) {
            int to = edges[e].other(v);
            if (!visited[to] && edges[e].capacityTo(to)) {
                edgeTo[to] = e;
                dfs(to);
            }
        }
    }

    bool hasPath(int start, int finish) {
        visited.assign(visited.size(), 0);
        dfs(start);
        return visited[finish];
    }

    int bottleneckCapacity(int start, int finish) {
        int bCapacity = 1e9;
        for (int v = finish; v != start; v = edges[edgeTo[v]].other(v))
            bCapacity = min(bCapacity, edges[edgeTo[v]].capacityTo(v));
        return bCapacity;
    }

    void addFlow(int start, int finish, int deltaFlow) {
        for (int v = finish; v != start; v = edges[edgeTo[v]].other(v))
            edges[edgeTo[v]].addFlowTo(v, deltaFlow);
    }

public:
    Graph(int vertexCount) :
        graph(vertexCount), visited(vertexCount), edgeTo(vertexCount) {}
        
    void addEdge(int from, int to, int capacity) {
        edges.push_back(Edge(from, to, capacity));
        graph[from].push_back(edges.size() - 1);
        graph[to].push_back(edges.size() - 1);
    }

    long long maxFlow(int start, int finish) {
        long long flow = 0;
        while (hasPath(start, finish)) {
            int deltaFlow = bottleneckCapacity(start, finish);
            addFlow(start, finish, deltaFlow);
            flow += deltaFlow;
        }
        return flow;
    }
};

Ссылки

Теория:

Демонстрация:

Код:

Задачи: