test/aoj/maximum_flow_dinic.test.cpp

• View this file on GitHub
• Last update: 2024-07-11 22:21:57+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/GRL_6_A

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/GRL_6_A"
#include "include/mtl/max_flow.hpp"
#include <bits/stdc++.h>
using namespace std;

int main() {
  int V,E; cin>>V>>E;
  Dinic G(V);
  for (int i = 0; i < E; i++) {
    int u,v,c; cin>>u>>v>>c;
    G.add_edge(u, v, c);
  }
  auto f = G.flow(0,V-1);
  cout << f << endl;
}

#line 1 "test/aoj/maximum_flow_dinic.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/GRL_6_A"
#line 2 "include/mtl/max_flow.hpp"
#include <limits>
#include <algorithm>
#include <vector>
#include <queue>
#include <cassert>
#include <iostream>

struct MaxFlowAlgorithm {
  virtual void add_edge(int u, int v, long long c) = 0;
  virtual long long flow(int s, int t, long long fup) = 0;
};

struct FlowPath {
  int t;
  long long cap;
  int rev;
  FlowPath(int t, long long flow, int rev) :
      t(t), cap(flow), rev(rev) {}
};

struct FordFulkerson : MaxFlowAlgorithm {
  std::vector<std::vector<FlowPath>> g;
  std::vector<bool> visited;
  explicit FordFulkerson(int n) : g(n), visited(n) {}

  void add_edge(int a, int b, long long f) override {
    g[a].emplace_back(b, f, g[b].size());
    g[b].emplace_back(a, 0, g[a].size()-1);
  }
  long long dfs(int t, int u, long long f) {
    if (visited[u])
      return 0;
    visited[u] = true;
    if (u == t)
      return f;
    for (auto& e : g[u]) {
      if (e.cap == 0) continue;
      auto flow = dfs(t, e.t, std::min(f, e.cap));
      if (flow) {
        e.cap -= flow;
        g[e.t][e.rev].cap += flow;
        return flow;
      }
    }
    return 0;
  }
  long long flow(int s, int t, long long fup) override {
    long long flow = 0;
    while (fup > 0) {
      visited.assign(g.size(), false);
      auto f = dfs(t, s, std::numeric_limits<long long>::max());
      if (f > 0) {
        flow += f;
        fup -= f;
      } else {
        break;
      }
    }
    return flow;
  }
  long long flow(int s, int t) {
    return flow(s, t, std::numeric_limits<long long>::max());
  }
};

struct Dinic : MaxFlowAlgorithm {
  std::vector<std::vector<FlowPath>> g;
  std::vector<std::vector<FlowPath>::iterator> nxt;
  std::vector<int> dist;
  explicit Dinic(int n) : g(n), nxt(n), dist(n) {}

  void add_edge(int a, int b, long long f) override {
    g[a].emplace_back(b, f, g[b].size());
    g[b].emplace_back(a, 0, g[a].size()-1);
  }
  long long dfs(int t, int u, long long f) {
    if (u == t) {
      return f;
    }
    long long fsum = 0;
    for (auto& it = nxt[u]; it != g[u].end() and fsum < f; ++it) {
      if (it->cap == 0 or dist[it->t] != dist[u]+1)
        continue;
      auto flow = dfs(t, it->t, std::min(f - fsum, it->cap));
      if (flow) {
        it->cap -= flow;
        g[it->t][it->rev].cap += flow;
        fsum += flow;
      }
    }
    return fsum;
  }
  long long flow(int s, int t, long long fup) override {
    long long flow = 0;
    std::queue<int> qs;
    while (fup) {
      // dual step
      std::transform(g.begin(), g.end(), nxt.begin(), [](auto& e) {
        return e.begin();
      });
      dist.assign(g.size(), std::numeric_limits<int>::max());
      qs.push(s);
      dist[s] = 0;
      while (!qs.empty()) {
        auto u = qs.front(); qs.pop();
        for (auto e : g[u]) {
          if (e.cap == 0 or dist[e.t] <= dist[u]+1)
            continue;
          dist[e.t] = dist[u]+1;
          if (e.t != t)
            qs.push(e.t);
        }
      }
      // primal step
      auto f = dfs(t, s, std::numeric_limits<long long>::max());
      if (f > 0) {
        flow += f;
        fup -= f;
      } else {
        break;
      }
    }
    return flow;
  }
  long long flow(int s, int t) {
    return flow(s, t, std::numeric_limits<long long>::max());
  }
};

using MaxFlowGraph = Dinic;

struct Matching {
  MaxFlowGraph G;
  int n,m,s,g;
  explicit Matching(int n, int m) : G(n+m+2), n(n), m(m), s(n+m), g(s+1) {
    for (int i = 0; i < n; i++)
      G.add_edge(s, i, 1);
    for (int i = 0; i < m; i++)
      G.add_edge(i+n, g, 1);
  }
  void add_edge(int a, int b) {
    G.add_edge(a, b+n, 1);
  }
  int flow() {
    return G.flow(s, g);
  }
  std::vector<std::pair<int,int>> matches() const {
    std::vector<std::pair<int,int>> ret;
    for (int i = 0; i < n; i++) {
      for (auto& e : G.g[i]) {
        if (e.t >= n and e.t < s and e.cap == 0) {
          ret.emplace_back(i, e.t-n);
        }
      }
    }
    return ret;
  }
};

// Project Selection Problem
template<typename P>
struct PSP {
  MaxFlowGraph G;
  int n,s,g;
  P psum;
  explicit PSP(int n) : G(n+2), n(n), s(n), g(s+1), psum(0) {};
  void add_profit(int a, P profit) {
    if (profit > 0)
      psum += profit;
    if (profit > 0)
      G.add_edge(a, g, profit);
    else if (profit < 0)
      G.add_edge(s, a, -profit);
  }
  void add_loss(int a, int b, P loss) {
    G.add_edge(a, b, loss);
  }
  P solve() {
    auto p = G.flow(s, g);
    return psum - p;
  }
  std::vector<bool> selections() const {
    std::vector<bool> sel(n, 1);
    for (auto& e : G.g[g]) {
      if (G.g[e.t][e.rev].cap > 0) {
        sel[e.t] = 0;
      }
    }
    return sel;
  }
};
#line 3 "test/aoj/maximum_flow_dinic.test.cpp"
#include <bits/stdc++.h>
using namespace std;

int main() {
  int V,E; cin>>V>>E;
  Dinic G(V);
  for (int i = 0; i < E; i++) {
    int u,v,c; cin>>u>>v>>c;
    G.add_edge(u, v, c);
  }
  auto f = G.flow(0,V-1);
  cout << f << endl;
}

Test cases

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

Back to top page