maxflow(最大流) (graph/maxflow.cpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2023-10-06 03:54:40+09:00

なにこれ

各辺に容量が設定される有向グラフ $G=(V,E)$ 中で，始点から終点まで流せる最大の流量を求める．

コンストラクタ

• maxflow(V)：V 頂点 $0$ 辺のグラフを作る．$V \leq 10^8$ 程度．

メンバ関数

• add(from, to, cap)：頂点 from から頂点 to へ容量 cap の有向辺を追加する．$0 \leq cap$
• solve(s, t)：頂点 s から頂点 t へ流せる最大の流量を返す．

計算量

$F$を最大流の流量とする．

• maxflow(V)：$O(V)$
• add(from, to, cap)：ならし $O(1)$
• solve(s, t)：$O(F(V+E))$

Verified with

• test/aoj_GRL_6_A.cpp
• test/aoj_GRL_7_A.cpp
• test/yuki_0177.cpp

Code

#pragma once

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

struct maxflow {
private:
	struct edge {
		int next;
		int rev;
		long long cap;

		edge(int next, int rev, long long cap) : next(next), rev(rev), cap(cap) {}
	};

	const int vnum;
	vector<vector<edge>> G;
	vector<int> used;
	int ts;

public:
	maxflow(int V) : vnum(V), G(V), used(V, -1), ts(0) {}

	void add(int from, int to, long long cap) {
		G[from].emplace_back(to, G[to].size(), cap);
		G[to].emplace_back(from, G[from].size() - 1, 0);
	}

private:
	long long dfs(int s, int t, long long flow) {
		if(s == t) return flow;
		used[s] = ts;
		for(edge &ed : G[s]) {
			if(used[ed.next] != ts && ed.cap > 0) {
				long long captmp = dfs(ed.next, t, min(flow, ed.cap));
				if(captmp > 0) {
					ed.cap -= captmp;
					G[ed.next][ed.rev].cap += captmp;
					return captmp;
				}
			}
		}
		return 0LL;
	}

public:
	long long solve(int s, int t) {
		long long res = 0, restmp;
		while((restmp = dfs(s, t, (1LL << 62) - 1)) > 0) {
			res += restmp;
			ts++;
		}
		return res;
	}
};

#line 2 "graph/maxflow.cpp"

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

struct maxflow {
private:
	struct edge {
		int next;
		int rev;
		long long cap;

		edge(int next, int rev, long long cap) : next(next), rev(rev), cap(cap) {}
	};

	const int vnum;
	vector<vector<edge>> G;
	vector<int> used;
	int ts;

public:
	maxflow(int V) : vnum(V), G(V), used(V, -1), ts(0) {}

	void add(int from, int to, long long cap) {
		G[from].emplace_back(to, G[to].size(), cap);
		G[to].emplace_back(from, G[from].size() - 1, 0);
	}

private:
	long long dfs(int s, int t, long long flow) {
		if(s == t) return flow;
		used[s] = ts;
		for(edge &ed : G[s]) {
			if(used[ed.next] != ts && ed.cap > 0) {
				long long captmp = dfs(ed.next, t, min(flow, ed.cap));
				if(captmp > 0) {
					ed.cap -= captmp;
					G[ed.next][ed.rev].cap += captmp;
					return captmp;
				}
			}
		}
		return 0LL;
	}

public:
	long long solve(int s, int t) {
		long long res = 0, restmp;
		while((restmp = dfs(s, t, (1LL << 62) - 1)) > 0) {
			res += restmp;
			ts++;
		}
		return res;
	}
};

Back to top page