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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
(Новая страница: « #include <stdio.h> #include <algorithm> #include <vector> #include <queue> using namespace std; struct Edge { int a, b, cap, flow; Edge(int a, i…»)
 
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
  #include <stdio.h>
  class Graph {
#include <algorithm>
    struct Edge {
#include <vector>
        int a, b, capacity, flow = 0;
#include <queue>
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) : a(a), b(b), cap(cap), flow(0) {}
    int other(int v) {
        int other(int v) const {
        return v == a ? b : a;
            return v == a ? b : a;
    }
        }
    int capTo(int v) {
        return v == b ? cap - flow : flow;
        int capacityTo(int v) const {
    }
            return v == b ? capacity - flow : flow;
    void addFlowTo(int v, int f) {
        }
        flow += (v == b ? f : -f);
    }
        void addFlowTo(int v, int deltaFlow) {
};
            flow += (v == b ? deltaFlow : -deltaFlow);
  vector<Edge> edges;
        }
    };
   
    vector<Edge> edges;
    vector<vector<int>> graph;
    vector<int> dist, edgeTo, index;
    bool bfs(int start, int finish) {
        dist.assign(graph.size(), 1e9);
        queue<int> q;
        dist[start] = 0;
        q.push(start);
   
   
int n, m, u[1010], p[1010], pos[1010];
        while (!q.empty()) {
vector<int> g[1010];
            int v = q.front();
            q.pop();
   
   
bool bfs(int v, int vTarget) {
             for (int e : graph[v]) {
    queue<int> q;
                int to = edges[e].other(v);
    u[v] = 1;
                if (edges[e].capacityTo(to) && dist[to] > dist[v] + 1) {
    q.push(v);
                    dist[to] = dist[v] + 1;
    while (!q.empty()) {
                    q.push(to);
        v = q.front();
                }
        q.pop();
        if (v == vTarget)
             return 1;
        for (int i = 0; i < g[v].size(); i++) {
            int e = g[v][i], to = edges[e].other(v);
            if (!u[to] && edges[e].capTo(to)) {
                p[to] = e;
                u[to] = u[v] + 1;
                q.push(to);
             }
             }
         }
         }
        return dist[finish] != 1e9;
     }
     }
    return 0;
}
   
   
bool dfs(int v, int vTarget) {
    bool dfs(int v, int finish) {
    if (v == vTarget)
        if (v == finish)
        return 1;
            return 1;
    for (; pos[v] < g[v].size(); pos[v]++) {
        int e = g[v][pos[v]], to = edges[e].other(v);
        for ( ; index[v] < graph[v].size(); index[v]++) {
        if (u[v] + 1 == u[to] && edges[e].capTo(to)) {
            int e = graph[v][index[v]], to = edges[e].other(v);
            p[to] = e;
            if (edges[e].capacityTo(to) && dist[to] == dist[v] + 1 && dfs(to, finish)) {
            if (dfs(to, vTarget))
                edgeTo[to] = e;
                 return 1;
                 return 1;
            }
         }
         }
        return 0;
     }
     }
    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));
        g[a - 1].push_back(edges.size() - 1);
         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);
         if (!bfs(0, n - 1))
    }
            break;
         fill(pos, pos + n, 0);
public:
         while (dfs(0, n - 1)) {
    Graph(int vertexCount) :
            int deltaFlow = 1 << 30;
         graph(vertexCount), dist(vertexCount), edgeTo(vertexCount), index(vertexCount) {}
            for (int v = n - 1; v != 0; v = edges[p[v]].other(v))
                deltaFlow = min(deltaFlow, edges[p[v]].capTo(v));
    void addEdge(int from, int to, int capacity) {
             flow += deltaFlow;
         edges.push_back(Edge(from, to, capacity));
            for (int v = n - 1; v != 0; v = edges[p[v]].other(v))
         graph[from].push_back(edges.size() - 1);
                 edges[p[v]].addFlowTo(v, deltaFlow);
        graph[to].push_back(edges.size() - 1);
    }
    long long maxFlow(int start, int finish) {
        long long flow = 0;
        while (bfs(start, finish)) {
            index.assign(graph.size(), 0);
             while (dfs(start, finish)) {
                int deltaFlow = bottleneckCapacity(start, finish);
                 addFlow(start, finish, deltaFlow);
                flow += deltaFlow;
            }
         }
         }
        return flow;
     }
     }
    printf("%d", flow);
  };
  }


== Ссылки ==
== Ссылки ==
* [http://e-maxx.ru/algo/dinic e-maxx.ru &mdash; Алгоритм Диница нахождения максимального потока]
Теория:
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D1%85%D0%B5%D0%BC%D0%B0_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%B0_%D0%94%D0%B8%D0%BD%D0%B8%D1%86%D0%B0 neerc.ifmo.ru/wiki &mdash; Схема алгоритма Диница]
* [http://e-maxx.ru/algo/dinic e-maxx.ru Алгоритм Диница нахождения максимального потока]
* [https://cp-algorithms.com/graph/dinic.html cp-algorithms.com — Maximum flow — Dinic's algorithm]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D1%85%D0%B5%D0%BC%D0%B0_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%B0_%D0%94%D0%B8%D0%BD%D0%B8%D1%86%D0%B0 neerc.ifmo.ru/wiki Схема алгоритма Диница]
* [https://wiki.algocode.ru/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B8%D0%BD%D0%B8%D1%86%D0%B0 wiki.algocode.ru — Алгоритм Диница]
* [https://codeforces.com/blog/entry/104960 codeforces.com — My way of understanding Dinic's algorithm]
* [https://usaco.guide/adv/max-flow?lang=cpp#dinics-algorithm usaco.guide — Dinic's Algorithm]
Демонстрация:
* [https://visualgo.net/en/maxflow visualgo.net — Network Flow]
Код:
* [https://github.com/indy256/codelibrary/blob/master/cpp/graphs/flows/max_flow_dinic.h indy256/codelibrary/cpp/graphs/flows/max_flow_dinic.h]
* [https://github.com/ADJA/algos/blob/master/Graphs/Dinic.cpp ADJA/algos/Graphs/Dinic.cpp]
Задачи:
* [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/MaxFlowDinic.java CodeLibrary &mdash; Dinic's algorithm in O(V^2 * E)]
* [http://github.com/ADJA/algos/blob/master/Graphs/Dinic.cpp Algos &mdash; MaxFlow Dinic algorithm with scaling. O(N * M * log(MC))]
* [http://visualgo.net/maxflow.html VisuAlgo &mdash; Network Flow]


[[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<int> dist, edgeTo, index;

    bool bfs(int start, int finish) {
        dist.assign(graph.size(), 1e9);
        queue<int> q;

        dist[start] = 0;
        q.push(start);

        while (!q.empty()) {
            int v = q.front();
            q.pop();

            for (int e : graph[v]) {
                int to = edges[e].other(v);
                if (edges[e].capacityTo(to) && dist[to] > dist[v] + 1) {
                    dist[to] = dist[v] + 1;
                    q.push(to);
                }
            }
        }

        return dist[finish] != 1e9;
    }

    bool dfs(int v, int finish) {
        if (v == finish)
            return 1;

        for ( ; index[v] < graph[v].size(); index[v]++) {
            int e = graph[v][index[v]], to = edges[e].other(v);
            if (edges[e].capacityTo(to) && dist[to] == dist[v] + 1 && dfs(to, finish)) {
                edgeTo[to] = e;
                return 1;
            }
        }

        return 0;
    }

    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), dist(vertexCount), edgeTo(vertexCount), index(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 (bfs(start, finish)) {
            index.assign(graph.size(), 0);
            while (dfs(start, finish)) {
                int deltaFlow = bottleneckCapacity(start, finish);
                addFlow(start, finish, deltaFlow);
                flow += deltaFlow;
            }
        }
        return flow;
    }
};

Ссылки

Теория:

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

Код:

Задачи: