This documentation is automatically generated by competitive-verifier/competitive-verifier
各辺に容量が設定される有向グラフ $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))$#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;
}
};