test/aoj/grl_6_a.test.cpp

View this file on GitHub
Last update: 2023-07-03 12:42:25+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/problems/GRL_6_A

Depends on

Code

// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/GRL_6_A

#include "src/cpp-template/header/int-alias.hpp"
#include "src/cpp-template/header/size-alias.hpp"
#include "src/graph/flow/max-flow.hpp"

#include <iostream>

namespace luz {

  void main_() {
    usize n, m;
    std::cin >> n >> m;

    MaxFlowGraph g(n);
    while (m--) {
      usize u, v;
      u32 c;
      std::cin >> u >> v >> c;
      g.add_directed_edge(u, v, c);
    }
    std::cout << g.max_flow(0, n - 1) << std::endl;
  }

} // namespace luz

int main() {
  luz::main_();
}

#line 1 "test/aoj/grl_6_a.test.cpp"
// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/GRL_6_A

#line 2 "src/cpp-template/header/int-alias.hpp"

#include <cstdint>

namespace luz {

  using i32 = std::int32_t;
  using i64 = std::int64_t;
  using u32 = std::uint32_t;
  using u64 = std::uint64_t;

}
#line 2 "src/cpp-template/header/size-alias.hpp"

#include <cstddef>

namespace luz {

  using isize = std::ptrdiff_t;
  using usize = std::size_t;

}
#line 2 "src/graph/flow/max-flow.hpp"

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

namespace luz {

  class MaxFlowGraph {
    using usize = std::size_t;
    using Cap = long long;

    struct Edge {
      usize to, rev;
      Cap cap;
    };

    usize n;
    std::vector< Cap > min_cost;
    std::vector< usize > iter;
    std::vector< std::vector< Edge > > g;

    bool build_augment_path(usize s, usize t) {
      min_cost.assign(n, -1);
      std::queue< usize > que;

      min_cost[s] = 0;
      que.push(s);

      while (not que.empty() and min_cost[t] == -1) {
        usize v = que.front();
        que.pop();

        for (const auto &e: g[v]) {
          if (e.cap > 0 and min_cost[e.to] == -1) {
            min_cost[e.to] = min_cost[v] + 1;
            que.push(e.to);
          }
        }
      }

      return min_cost[t] != -1;
    }

    Cap find_augment_path(usize v, usize t, Cap flow_limit) {
      if (v == t) return flow_limit;

      for (usize &i = iter[v]; i < g[v].size(); i++) {
        Edge &e = g[v][i];

        if (e.cap > 0 and min_cost[v] + 1 == min_cost[e.to]) {
          Cap d = find_augment_path(e.to, t, std::min(flow_limit, e.cap));

          if (d > 0) {
            e.cap -= d;
            g[e.to][e.rev].cap += d;
            return d;
          }
        }
      }

      return 0;
    }

   public:
    const Cap INF = std::numeric_limits< Cap >::max();

    explicit MaxFlowGraph(usize n): n(n), g(n) {}

    usize add_directed_edge(usize from, usize to, Cap cap) {
      // assert(from < n and to < n and from != to);
      usize idx = g[from].size();
      g[from].emplace_back(Edge { to, g[to].size(), cap });
      g[to].emplace_back(Edge { from, idx, 0 });
      return idx;
    }

    // 1. O(n^2 m) in general
    // 2. other case: see docs "dinic-time-complexity.pdf"
    Cap max_flow(usize s, usize t, Cap flow_limit) {
      // assert(s < n and t < n and s != t);
      Cap flow = 0, add = 0;

      while (build_augment_path(s, t) and flow < flow_limit) {
        iter.assign(n, 0);

        do {
          add = find_augment_path(s, t, flow_limit - add);
          flow += add;
        } while (add > 0);
      }

      return flow;
    }

    Cap max_flow(usize s, usize t) {
      return max_flow(s, t, INF);
    }

    // === no need to implement from here ===
    // to use F += link(s, t, ...)
    Cap link(usize s, usize t, usize from, usize idx, Cap f){
      g[from][idx].cap += f;
      return max_flow(s, t, f);
    }

    // to use F += cut(s, t, ...)
    Cap cut(usize s, usize t, usize from, usize idx){
      auto &e = g[from][idx];
      usize to = e.to;
      Cap rem = g[to][e.rev].cap;

      if(rem == 0) return e.cap = 0;
      e.cap = g[to][e.rev].cap = 0;

      Cap cap = rem - max_flow(from, to, rem);
      if (from != s and cap != 0) max_flow(from, s, cap);
      if (t != to and cap != 0) max_flow(t, to, cap);
      return -cap;
    }

  };

} // namespace luz
#line 6 "test/aoj/grl_6_a.test.cpp"

#include <iostream>

namespace luz {

  void main_() {
    usize n, m;
    std::cin >> n >> m;

    MaxFlowGraph g(n);
    while (m--) {
      usize u, v;
      u32 c;
      std::cin >> u >> v >> c;
      g.add_directed_edge(u, v, c);
    }
    std::cout << g.max_flow(0, n - 1) << std::endl;
  }

} // namespace luz

int main() {
  luz::main_();
}