グラフ/フロー/最大流/Ford–Fulkerson 法
(test/graph/flow/maximum_flow/ford-fulkerson.test.cpp)

• View this file on GitHub
• Last update: 2023-02-25 16:35:06+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A

Depends on

• Ford–Fulkerson 法 (include/emthrm/graph/flow/maximum_flow/ford-fulkerson.hpp)

Code

/*
 * @title グラフ/フロー/最大流/Ford–Fulkerson 法
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A
 */

#include <iostream>

#include "emthrm/graph/flow/maximum_flow/ford-fulkerson.hpp"

int main() {
  int v, e;
  std::cin >> v >> e;
  emthrm::FordFulkerson<long long> ford_fulkerson(v);
  while (e--) {
    int u_i, v_i, c_i;
    std::cin >> u_i >> v_i >> c_i;
    ford_fulkerson.add_edge(u_i, v_i, c_i);
  }
  std::cout << ford_fulkerson.maximum_flow(0, v - 1) << '\n';
  return 0;
}

#line 1 "test/graph/flow/maximum_flow/ford-fulkerson.test.cpp"
/*
 * @title グラフ/フロー/最大流/Ford–Fulkerson 法
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A
 */

#include <iostream>

#line 1 "include/emthrm/graph/flow/maximum_flow/ford-fulkerson.hpp"



#include <algorithm>
#include <limits>
#include <vector>

namespace emthrm {

template <typename T>
struct FordFulkerson {
  struct Edge {
    int dst, rev;
    T cap;
    explicit Edge(const int dst, const T cap, const int rev)
        : dst(dst), rev(rev), cap(cap) {}
  };

  std::vector<std::vector<Edge>> graph;

  explicit FordFulkerson(const int n)
      : graph(n), timestamp(0), is_used(n, -1) {}

  void add_edge(const int src, const int dst, const T cap) {
    graph[src].emplace_back(dst, cap, graph[dst].size());
    graph[dst].emplace_back(src, 0, graph[src].size() - 1);
  }

  T maximum_flow(const int s, const int t,
                 T limit = std::numeric_limits<T>::max()) {
    T res = 0;
    while (limit > 0) {
      const T tmp = dfs(s, t, limit);
      ++timestamp;
      if (tmp == 0) break;
      limit -= tmp;
      res += tmp;
    }
    return res;
  }

 private:
  int timestamp;
  std::vector<int> is_used;

  T dfs(const int ver, const int t, const T flow) {
    if (ver == t) return flow;
    is_used[ver] = timestamp;
    for (Edge& e : graph[ver]) {
      if (is_used[e.dst] < timestamp && e.cap > 0) {
        const T tmp = dfs(e.dst, t, std::min(flow, e.cap));
        if (tmp > 0) {
          e.cap -= tmp;
          graph[e.dst][e.rev].cap += tmp;
          return tmp;
        }
      }
    }
    return 0;
  }
};

}  // namespace emthrm


#line 10 "test/graph/flow/maximum_flow/ford-fulkerson.test.cpp"

int main() {
  int v, e;
  std::cin >> v >> e;
  emthrm::FordFulkerson<long long> ford_fulkerson(v);
  while (e--) {
    int u_i, v_i, c_i;
    std::cin >> u_i >> v_i >> c_i;
    ford_fulkerson.add_edge(u_i, v_i, c_i);
  }
  std::cout << ford_fulkerson.maximum_flow(0, v - 1) << '\n';
  return 0;
}

Back to top page