mmrz's library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by mm-rz Hosted on GitHub Pages — Theme by mattgraham

最大流(Ford-Fulkerson)
(graph/ford_fulkerson.hpp)

• View this file on GitHub
• Last update: 2025-07-01 03:22:56+09:00
• Include: #include "graph/ford_fulkerson.hpp"

最大流(Ford-Fulkerson)

使い方

• ford_fulkerson<T>(int V) : 頂点数 $V$ の最大流グラフのコンストラクタ
• void add edge(int a, int b, T c) : $a$ から $b$ に容量 $c$ の辺を張る
• T calc(int a, int b) $a$ から $b$ への最大流を求める。辺中を流れる最大流量を $f$, 辺数 $E$ とすると、最悪計算量 $O(fE)$

Verified with

• verify/aoj/grl/6_A___ford_fulkerson.test.cpp

Code

#pragma once

#include<vector>
#include<limits>

template<typename T>
struct ford_fulkerson {

	struct edge{
		int to;
		T cap;
		T rev;
	};

	int n;
	std::vector<std::vector<edge>> G;
	std::vector<bool> used;

	ford_fulkerson(int _v) : n(_v), G(n), used(n) {}

	void add_edge(int from, int to, T cap){
		G[from].push_back((edge){to, cap, (T)G[to].size()});
		G[to].push_back((edge){from, 0, (T)(G[from].size() - 1)});
	}

	T dfs(int v, int t, T f){
		if(v == t)return f;
		used[v] = true;
		for(int i = 0;i < (int)G[v].size();i++){
			edge &e = G[v][i];
			if(!used[e.to] && e.cap > 0){
				T d = dfs(e.to, t, min(f, e.cap));
				if(d > 0){
					e.cap -= d;
					G[e.to][e.rev].cap += d;
					return d;
				}
			}
		}
		return 0;
	}

	T calc(int s, int t){
		T flow = 0;
		for(;;){
			for(int i = 0;i < n;i++)used[i] = false;
			T f = dfs(s, t, std::numeric_limits<T>::max());
			if(f == 0)return flow;
			flow += f;
		}
	}
};

#line 2 "graph/ford_fulkerson.hpp"

#include<vector>
#include<limits>

template<typename T>
struct ford_fulkerson {

	struct edge{
		int to;
		T cap;
		T rev;
	};

	int n;
	std::vector<std::vector<edge>> G;
	std::vector<bool> used;

	ford_fulkerson(int _v) : n(_v), G(n), used(n) {}

	void add_edge(int from, int to, T cap){
		G[from].push_back((edge){to, cap, (T)G[to].size()});
		G[to].push_back((edge){from, 0, (T)(G[from].size() - 1)});
	}

	T dfs(int v, int t, T f){
		if(v == t)return f;
		used[v] = true;
		for(int i = 0;i < (int)G[v].size();i++){
			edge &e = G[v][i];
			if(!used[e.to] && e.cap > 0){
				T d = dfs(e.to, t, min(f, e.cap));
				if(d > 0){
					e.cap -= d;
					G[e.to][e.rev].cap += d;
					return d;
				}
			}
		}
		return 0;
	}

	T calc(int s, int t){
		T flow = 0;
		for(;;){
			for(int i = 0;i < n;i++)used[i] = false;
			T f = dfs(s, t, std::numeric_limits<T>::max());
			if(f == 0)return flow;
			flow += f;
		}
	}
};

Back to top page