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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Строка 88: Строка 88:
== Ссылки ==
== Ссылки ==
Теория:
Теория:
* [http://algs4.cs.princeton.edu/lectures/64MaxFlow.pdf algs4.cs.princeton.edu/lectures — 6.4 Maximum Flow]
* [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://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]
* [http://brilliant.org/wiki/ford-fulkerson-algorithm Brilliant.org — Ford-Fulkerson Algorithm]
Демонстрация:
Демонстрация:
* [http://visualgo.net/maxflow.html VisuAlgo — Network Flow]
* [https://visualgo.net/en/maxflow VisuAlgo Network Flow]
Код:
Код:
* [http://github.com/indy256/codelibrary/blob/master/java/src/MaxFlowFordFulkerson.java CodeLibrary — Maximum flow. Ford-Fulkerson alogithm in O(V^2 * 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 — Ford-Fulkerson maxflow]
* [http://github.com/ADJA/algos/blob/master/Graphs/FordFulkerson.cpp Algos — Ford-Fulkerson maxflow]
* algs4.cs.princeton.edu/code — [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] (несмотря на название, используется алгоритм Эдмондса-Карпа)
* algs4.cs.princeton.edu/code — [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] (несмотря на название, используется алгоритм Эдмондса-Карпа)

Версия от 23:11, 22 сентября 2020

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

class Edge {
    int a, b, capacity, flow;
public:
    Edge(int a, int b, int capacity) : a(a), b(b), capacity(capacity), flow(0) {}
    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 f) {
        flow += (v == b ? f : -f);
    }
};

class Graph {
    vector<Edge> edges;
    vector<vector<int>> g;
    vector<bool> used;
    vector<int> edgeTo;
    void dfs(int v) {
        used[v] = 1;
        for (int e : g[v]) {
            int to = edges[e].other(v);
            if (!used[to] && edges[e].capacityTo(to) > 0) {
                edgeTo[to] = e;
                dfs(to);
            }
        }
    }
    bool hasPath(int from, int to) {
        fill(used.begin(), used.end(), 0);
        dfs(from);
        return used[to];
    }
    int bottleneckCapacity(int from, int to) {
        int bCapacity = 1e9;
        for (int v = to; v != from; v = edges[edgeTo[v]].other(v))
            bCapacity = min(bCapacity, edges[edgeTo[v]].capacityTo(v));
        return bCapacity;
    }
    void addFlow(int from, int to, int flow) {
        for (int v = to; v != from; v = edges[edgeTo[v]].other(v))
            edges[edgeTo[v]].addFlowTo(v, flow);
    }
public:
    Graph(int verticesCount) {
        g.resize(verticesCount);
        used.resize(verticesCount);
        edgeTo.resize(verticesCount);
    }
    void addEdge(int from, int to, int capacity) {
        edges.push_back(Edge(from, to, capacity));
        g[from].push_back(edges.size() - 1);
        g[ to ].push_back(edges.size() - 1);
    }
    long long maxFlow(int from, int to) {
        long long flow = 0;
        while (hasPath(from, to)) {
            int deltaFlow = bottleneckCapacity(from, to);
            addFlow(from, to, deltaFlow);
            flow += deltaFlow;
        }
        return flow;
    }
};


int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    Graph g(n);

    int a, b, c;
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &a, &b, &c);
        g.addEdge(a - 1, b - 1, c);
    }

    printf("%lld", g.maxFlow(0, n - 1));
}

Ссылки

Теория:

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

Код:

Задачи: