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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Строка 1: Строка 1:
  #include <stdio.h>
  class Graph {
  #include <algorithm>
    struct Edge {
  #include <vector>
        int a, b, capacity, flow;
using namespace std;
   
        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;
        }
   
   
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 f) {
         return v == a ? b : a;
            flow += (v == b ? f : -f);
    }
        }
    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>> g;
     vector<bool> used;
     vector<bool> visited;
     vector<int> edgeTo;
     vector<int> edgeTo;
     void dfs(int v) {
     void dfs(int v) {
         used[v] = 1;
         visited[v] = 1;
         for (int e : g[v]) {
         for (int e : g[v]) {
             int to = edges[e].other(v);
             int to = edges[e].other(v);
             if (!used[to] && edges[e].capacityTo(to) > 0) {
             if (!visited[to] && edges[e].capacityTo(to) > 0) {
                 edgeTo[to] = e;
                 edgeTo[to] = e;
                 dfs(to);
                 dfs(to);
Строка 34: Строка 34:
         }
         }
     }
     }
     bool hasPath(int from, int to) {
     bool hasPath(int from, int to) {
         fill(used.begin(), used.end(), 0);
         fill(visited.begin(), visited.end(), 0);
         dfs(from);
         dfs(from);
         return used[to];
         return visited[to];
     }
     }
     int bottleneckCapacity(int from, int to) {
     int bottleneckCapacity(int from, int to) {
         int bCapacity = 1e9;
         int bCapacity = 1e9;
Строка 45: Строка 47:
         return bCapacity;
         return bCapacity;
     }
     }
     void addFlow(int from, int to, int flow) {
     void addFlow(int from, int to, int flow) {
         for (int v = to; v != from; v = edges[edgeTo[v]].other(v))
         for (int v = to; v != from; v = edges[edgeTo[v]].other(v))
             edges[edgeTo[v]].addFlowTo(v, flow);
             edges[edgeTo[v]].addFlowTo(v, flow);
     }
     }
  public:
  public:
     Graph(int verticesCount) {
     Graph(int vertexCount) {
         g.resize(verticesCount);
         g.resize(vertexCount);
         used.resize(verticesCount);
         visited.resize(vertexCount);
         edgeTo.resize(verticesCount);
         edgeTo.resize(vertexCount);
     }
     }
     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);
         g[from].push_back(edges.size() - 1);
         g[ to ].push_back(edges.size() - 1);
         g[to].push_back(edges.size() - 1);
     }
     }
     long long maxFlow(int from, int to) {
     long long maxFlow(int from, int to) {
         long long flow = 0;
         long long flow = 0;
Строка 70: Строка 76:
     }
     }
  };
  };
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));
}


== Ссылки ==
== Ссылки ==

Версия от 02:52, 26 декабря 2021

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

        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);
        }
    };

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

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

    bool hasPath(int from, int to) {
        fill(visited.begin(), visited.end(), 0);
        dfs(from);
        return visited[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 vertexCount) {
        g.resize(vertexCount);
        visited.resize(vertexCount);
        edgeTo.resize(vertexCount);
    }

    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;
    }
};

Ссылки

Теория:

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

Код:

Задачи:

Источник — https://acm.khpnets.info/w39/index.php?title=Алгоритм_Форда-Фалкерсона&oldid=2742