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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
(не показано 5 промежуточных версий этого же участника)
Строка 1: Строка 1:
  #include <stdio.h>
  class Graph {
  #include <algorithm>
    struct Edge {
  #include <vector>
        int a, b, capacity, flow = 0;
#include <queue>
   
using namespace std;
        Edge(int a, int b, int capacity) :
            a(a), b(b), capacity(capacity) {}
   
        int other(int v) const {
            return v == a ? b : a;
        }
   
   
class Edge {
         int capacityTo(int v) const {
    int a, b, capacity, flow;
            return v == b ? capacity - flow : flow;
public:
        }
    Edge(int a, int b, int capacity) : a(a), b(b), capacity(capacity), flow(0) {}
    int other(int v) const {
        void addFlowTo(int v, int deltaFlow) {
         return v == a ? b : a;
            flow += (v == b ? deltaFlow : -deltaFlow);
    }
        }
    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<Edge> edges;
     vector< vector<int> > g;
     vector<vector<int>> graph;
     vector<bool> used;
     vector<bool> visited;
     vector<int> edgeTo;
     vector<int> edgeTo;
     void bfs(int v) {
     void bfs(int start) {
         queue<int> q;
         queue<int> q;
         used[v] = 1;
         visited[start] = 1;
         q.push(v);
         q.push(start);
         while (!q.empty()) {
         while (!q.empty()) {
             v = q.front();
             int v = q.front();
             q.pop();
             q.pop();
             for (int i = 0; i < g[v].size(); i++) {
             for (int e : graph[v]) {
                 int e = g[v][i], to = edges[e].other(v);
                 int to = edges[e].other(v);
                 if (!used[to] && edges[e].capacityTo(to)) {
                 if (!visited[to] && edges[e].capacityTo(to)) {
                     edgeTo[to] = e;
                     edgeTo[to] = e;
                     used[to] = 1;
                     visited[to] = 1;
                     q.push(to);
                     q.push(to);
                 }
                 }
Строка 42: Строка 41:
         }
         }
     }
     }
     bool hasPath(int from, int to) {
         fill(used.begin(), used.end(), 0);
     bool hasPath(int start, int finish) {
         bfs(from);
         visited.assign(visited.size(), 0);
         return used[to];
         bfs(start);
         return visited[finish];
     }
     }
     int bottleneckCapacity(int from, int to) {
         int bCapacity = 1 << 30;
     int bottleneckCapacity(int start, int finish) {
         for (int v = to; v != from; v = edges[edgeTo[v]].other(v))
         int bCapacity = 1e9;
         for (int v = finish; v != start; v = edges[edgeTo[v]].other(v))
             bCapacity = min(bCapacity, edges[edgeTo[v]].capacityTo(v));
             bCapacity = min(bCapacity, edges[edgeTo[v]].capacityTo(v));
         return bCapacity;
         return bCapacity;
     }
     }
     void addFlow(int from, int to, int flow) {
         for (int v = to; v != from; v = edges[edgeTo[v]].other(v))
     void addFlow(int start, int finish, int deltaFlow) {
             edges[edgeTo[v]].addFlowTo(v, flow);
         for (int v = finish; v != start; v = edges[edgeTo[v]].other(v))
             edges[edgeTo[v]].addFlowTo(v, deltaFlow);
     }
     }
  public:
  public:
     Graph(int verticesCount) {
     Graph(int vertexCount) :
         g.resize(verticesCount);
         graph(vertexCount), visited(vertexCount), edgeTo(vertexCount) {}
        used.resize(verticesCount);
        edgeTo.resize(verticesCount);
    }
     void addEdge(int from, int to, int capacity) {
     void addEdge(int from, int to, int capacity) {
         edges.push_back(Edge(from, to, capacity));
         edges.push_back(Edge(from, to, capacity));
         g[from].push_back(edges.size() - 1);
         graph[from].push_back(edges.size() - 1);
         g[to].push_back(edges.size() - 1);
         graph[to].push_back(edges.size() - 1);
     }
     }
     long long maxFlow(int from, int to) {
     long long maxFlow(int start, int finish) {
         long long flow = 0;
         long long flow = 0;
         while (hasPath(from, to)) {
         while (hasPath(start, finish)) {
             int deltaFlow = bottleneckCapacity(from, to);
             int deltaFlow = bottleneckCapacity(start, finish);
             addFlow(from, to, deltaFlow);
             addFlow(start, finish, deltaFlow);
             flow += deltaFlow;
             flow += deltaFlow;
         }
         }
Строка 78: Строка 80:
     }
     }
  };
  };
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));
}


== Ссылки ==
== Ссылки ==
Теория:
Теория:
:* [http://algs4.cs.princeton.edu/lectures/64MaxFlow.pdf algs4.cs.princeton.edu/lectures &mdash; 6.4 Maximum Flow]
* [https://algs4.cs.princeton.edu/lectures/keynote/64MaxFlow.pdf algs4.cs.princeton.edu 6.4 Maximum Flow]
:* [http://e-maxx.ru/algo/edmonds_karp e-maxx.ru &mdash; Алгоритм Эдмондса-Карпа нахождения максимального потока за O (NM^2)]
* [http://e-maxx.ru/algo/edmonds_karp e-maxx.ru Алгоритм Эдмондса-Карпа нахождения максимального потока за O (NM^2)]
:* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%AD%D0%B4%D0%BC%D0%BE%D0%BD%D0%B4%D1%81%D0%B0-%D0%9A%D0%B0%D1%80%D0%BF%D0%B0 neerc.ifmo.ru/wiki &mdash; Алгоритм Эдмондса-Карпа]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%AD%D0%B4%D0%BC%D0%BE%D0%BD%D0%B4%D1%81%D0%B0-%D0%9A%D0%B0%D1%80%D0%BF%D0%B0 neerc.ifmo.ru/wiki Алгоритм Эдмондса-Карпа]
* [http://brilliant.org/wiki/edmonds-karp-algorithm Brilliant.org — Edmonds-Karp Algorithm]
Демонстрация:
Демонстрация:
:* [http://visualgo.net/maxflow.html VisuAlgo &mdash; Network Flow]
* [https://visualgo.net/en/maxflow VisuAlgo Network Flow]
Код:
Код:
:* [http://github.com/indy256/codelibrary/blob/master/java/src/MaxFlowEdmondsKarp.java CodeLibrary &mdash; Maximum flow. Edmonds-Karp algorithm in O(min(E^2 * V, E * FLOW))]
* [https://github.com/indy256/codelibrary/blob/master/java/graphs/flows/MaxFlowEdmondsKarp.java CodeLibrary &mdash; Maximum flow. Edmonds-Karp algorithm in O(min(E^2 * V, E * FLOW))]
:* algs4.cs.princeton.edu/code &mdash; [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/FlowEdge.java.html FlowEdge], [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/FlowNetwork.java.html FlowNetwork], [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/FordFulkerson.java.html FordFulkerson] (несмотря на название, используется алгоритм Эдмондса-Карпа)
* 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]
:* [[:Категория:Задачи: Максимальный поток|Задачи: Максимальный поток]]
* [[:Категория:Задачи: Максимальный поток|Задачи: Максимальный поток]]


[[Category: Максимальный поток]]
[[Category: Максимальный поток]]

Текущая версия от 00:59, 3 января 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 bfs(int start) {
        queue<int> q;
        visited[start] = 1;
        q.push(start);
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (int e : graph[v]) {
                int to = edges[e].other(v);
                if (!visited[to] && edges[e].capacityTo(to)) {
                    edgeTo[to] = e;
                    visited[to] = 1;
                    q.push(to);
                }
            }
        }
    }

    bool hasPath(int start, int finish) {
        visited.assign(visited.size(), 0);
        bfs(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;
    }
};

Ссылки

Теория:

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

Код:

Задачи: