Ford Fulkerson (maximum flow)
(graph/fordFulkerson.hpp)

• View this file on GitHub
• Last update: 2022-09-24 17:12:36+09:00
• Include: #include "graph/fordFulkerson.hpp"

概要

• 最大フローを求めるアルゴリズム

実装のヒント

• 残余グラフを使う
• dfsで残余グラフを探索して、スタートからゴールまでのパスとそのコストの最小値を求める。 $O(E)$
• そのパスに流せるだけ(パスの最小コスト）流す。
• これを残余グラフのパスがなくなるまで繰り返す。繰り返しの回数は最大で再流量回$F$となる。
• 全体の計算量は$O(FE)$

Verified with

• test/graph/fordFulkerson.aoj_GRL_6_A.test.cpp

Code

#pragma once
#include <limits>
#include <vector>
using namespace std;

template <typename T>
struct FordFulkerson {
  struct Edge {
    int to;
    T cost;
    int rev;
  };

 public:
  int size_ = 0;
  vector<bool> used;
  vector<vector<Edge>> G;

  FordFulkerson(int size) : size_(size), used(size), G(size) {}

  void add_edge(int from, int to, T cap) {
    G[from].push_back({to, cap, (int)G[to].size()});
    G[to].push_back({from, 0, (int)G[from].size() - 1});
  }

  T max_flow(int s, int t) {
    T total_flow = 0;
    while (true) {
      fill(used.begin(), used.end(), false);
      T INF = numeric_limits<T>::max();
      T F = dfs(s, t, INF);
      if (F == 0) break;
      total_flow += F;
    }
    return total_flow;
  }

 private:
  T dfs(int pos, int goal, T F) {
    if (pos == goal) return F;
    used[pos] = true;
    for (int i = 0; i < (int)G[pos].size(); i++) {
      auto &e = G[pos][i];
      if (!used[e.to] && e.cost > 0) {
        T d = dfs(e.to, goal, min(F, e.cost));
        if (d > 0) {
          e.cost -= d;
          G[e.to][e.rev].cost += d;
          return d;
        }
      }
    }
    return 0;
  }
};

#line 2 "graph/fordFulkerson.hpp"
#include <limits>
#include <vector>
using namespace std;

template <typename T>
struct FordFulkerson {
  struct Edge {
    int to;
    T cost;
    int rev;
  };

 public:
  int size_ = 0;
  vector<bool> used;
  vector<vector<Edge>> G;

  FordFulkerson(int size) : size_(size), used(size), G(size) {}

  void add_edge(int from, int to, T cap) {
    G[from].push_back({to, cap, (int)G[to].size()});
    G[to].push_back({from, 0, (int)G[from].size() - 1});
  }

  T max_flow(int s, int t) {
    T total_flow = 0;
    while (true) {
      fill(used.begin(), used.end(), false);
      T INF = numeric_limits<T>::max();
      T F = dfs(s, t, INF);
      if (F == 0) break;
      total_flow += F;
    }
    return total_flow;
  }

 private:
  T dfs(int pos, int goal, T F) {
    if (pos == goal) return F;
    used[pos] = true;
    for (int i = 0; i < (int)G[pos].size(); i++) {
      auto &e = G[pos][i];
      if (!used[e.to] && e.cost > 0) {
        T d = dfs(e.to, goal, min(F, e.cost));
        if (d > 0) {
          e.cost -= d;
          G[e.to][e.rev].cost += d;
          return d;
        }
      }
    }
    return 0;
  }
};

Back to top page