test/graph/dinic.test.cpp

• View this file on GitHub
• Last update: 2025-10-17 14:01:51+08:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A

Depends on

• src/graph/dinic.hpp

Code

// competitive-verifier: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A
#include <bits/stdc++.h>
#define PUSHB push_back
#define ALL(a) (a).begin(), (a).end()
using namespace std;
using ll = long long;

#include "../../src/graph/dinic.hpp"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  Dinic<ll> dinic(n);
  for (int _ = 0; _ < m; _++) {
    int u, v, c;
    cin >> u >> v >> c;
    dinic.adde(u, v, c);
  }
  cout << dinic.flow(0, n - 1) << "\n";
  return 0;
}

#line 1 "test/graph/dinic.test.cpp"
// competitive-verifier: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A
#include <bits/stdc++.h>
#define PUSHB push_back
#define ALL(a) (a).begin(), (a).end()
using namespace std;
using ll = long long;

#line 1 "src/graph/dinic.hpp"
// 时间复杂度: 一般图 $\mathcal{O}(n^2 m)$, 二分图匹配 $\mathcal{O}(m \sqrt{n})$.
template <typename T>
struct Dinic {
  struct Edge {
    int u, v;
    T cap, flow;
  };
  static constexpr T INF = numeric_limits<T>::max();
  int _s, _t;
  vector<int> cur, h;
  vector<vector<int>> G;
  vector<Edge> E;
  Dinic(int n) : cur(n), h(n), G(n) {}
  void adde(int u, int v, T cap) {
    G[u].PUSHB(E.size()), E.PUSHB({u, v, cap, 0});
    G[v].PUSHB(E.size()), E.PUSHB({v, u, 0, 0});
  }
  T flow(int s, int t) {
    _s = s, _t = t;
    T ret = 0;
    while (bfs()) {
      fill(ALL(cur), 0);
      ret += dfs(s, INF);
    }
    return ret;
  }

 public:
  bool bfs() {
    fill(ALL(h), -1);
    queue<int> que;
    h[_s] = 0;
    que.push(_s);
    while (!que.empty()) {
      int u = que.front();
      que.pop();
      for (int i : G[u]) {
        const auto& [_, v, cap, flow] = E[i];
        if (h[v] != -1 || cap <= flow) continue;
        h[v] = h[u] + 1;
        que.push(v);
        if (v == _t) return true;
      }
    }
    return false;
  }
  T dfs(int u, T up) {
    if (u == _t) return up;
    T rest = up;
    for (int& i = cur[u]; i < int(G[u].size()); i++) {
      auto& [_, v, cap, flow] = E[G[u][i]];
      if (h[v] != h[u] + 1 || cap <= flow) continue;
      T f = dfs(v, min(rest, cap - flow));
      if (f <= 0) continue;
      flow += f;
      E[G[u][i] ^ 1].flow -= f;
      rest -= f;
      if (rest == 0) break;
    }
    return up - rest;
  }
};
#line 9 "test/graph/dinic.test.cpp"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  Dinic<ll> dinic(n);
  for (int _ = 0; _ < m; _++) {
    int u, v, c;
    cin >> u >> v >> c;
    dinic.adde(u, v, c);
  }
  cout << dinic.flow(0, n - 1) << "\n";
  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	5 ms	4 MB
g++	01_small_00.in	AC	4 ms	4 MB
g++	01_small_01.in	AC	4 ms	4 MB
g++	01_small_02.in	AC	4 ms	4 MB
g++	01_small_03.in	AC	4 ms	4 MB
g++	02_corner_00.in	AC	4 ms	4 MB
g++	02_corner_01.in	AC	4 ms	4 MB
g++	02_corner_02.in	AC	4 ms	4 MB
g++	02_corner_03.in	AC	4 ms	4 MB
g++	03_random_00.in	AC	4 ms	4 MB
g++	03_random_01.in	AC	4 ms	4 MB
g++	03_random_02.in	AC	4 ms	4 MB
g++	03_random_03.in	AC	4 ms	4 MB
g++	03_random_04.in	AC	4 ms	4 MB
g++	03_random_05.in	AC	4 ms	4 MB
g++	03_random_06.in	AC	4 ms	4 MB
g++	03_random_07.in	AC	4 ms	4 MB
g++	04_rand_00.in	AC	4 ms	4 MB
g++	04_rand_01.in	AC	4 ms	4 MB
g++	04_rand_02.in	AC	4 ms	4 MB
g++	04_rand_03.in	AC	4 ms	4 MB
g++	04_rand_04.in	AC	4 ms	4 MB
g++	04_rand_05.in	AC	4 ms	4 MB
g++	04_rand_06.in	AC	4 ms	4 MB
g++	04_rand_07.in	AC	4 ms	4 MB
g++	05_large_00.in	AC	4 ms	4 MB
g++	05_large_01.in	AC	4 ms	4 MB
g++	05_large_02.in	AC	4 ms	4 MB
g++	05_large_03.in	AC	4 ms	4 MB
g++	05_large_04.in	AC	4 ms	4 MB
g++	05_large_05.in	AC	4 ms	4 MB
g++	06_biased_00.in	AC	4 ms	4 MB
g++	06_biased_01.in	AC	4 ms	4 MB
g++	06_biased_02.in	AC	4 ms	4 MB
g++	06_biased_03.in	AC	4 ms	4 MB
g++	06_biased_04.in	AC	4 ms	4 MB
g++	06_biased_05.in	AC	4 ms	4 MB
g++	06_biased_06.in	AC	4 ms	4 MB
g++	06_biased_07.in	AC	5 ms	4 MB
g++	06_biased_08.in	AC	4 ms	4 MB

Back to top page