网络流概念细节：
1.流：出流量-入流量。割：一个V的划分，把s，t分开。
2.最大流：安排每条边的流量，使得图的流最大。最小割：一个划分，使得割的容量尽可能小。（割的容量：所有S到T的边的容量之和，不算T到S的边）
3.任取一个流，它比最大流劣在哪里，任取一个割，它比最小割劣在哪里？
一个引理：任取一个流和一个割，有$f\leqslant ||S,T||$，等号成立当且仅当所有S到T的边满流，T到S的边空流。而不是所有的流和割都能使得等号成立。
举个例子，有网络：$(s,1,1),(1,3,1),(s,2,1),(2,3,1),(2,4,1),(3,t,1),(4,t,2)$;
有$S=\{s,1,2,3\}，T=\{4,t\}$是一个最小割，$S=\{s,1,2,4\},T=\{3,t\}$则不是，因为不可能使得到点3的边满流，也不可能使得点4到t满流，因为容量限制和流守恒性。
4.最大流最小割定理：最大流=最小割
EK算法
算法思想：
1.根据残量网络Gf，如果存在一条增广路，能使得s到t，则说明能增大这条增广路上所有的边1的流量而不违反流守恒性和容量限制，因此图的流量会增大。
2.我们一直增广直到不能增广，此时图的流量不能再增加。
3.找到一条增广路，可以使用BFS，时间复杂度O(E)。如果要求最大流，应该使得我们的增广次数是最多的。但是 增广的先后顺序会影响最终增广的次数，如上面的例子，最优解应该是增广s到2到4到t，和s到1到3到t。但是如果先增广了s到2到3到t，则不存在增广路。
4.容易想到如果dfs的话能穷尽s到t的所有路径，类似的思想，如果我们增广的时候能“反悔”（dfs的回溯）的话，就能找到最优的增广路。为了支持这个“反悔”的操作，我们在给一条边加上流量f(u,v)的时候，同时建立一条反向边，为这条反向边加上-f(u,v)的流量。这样在下次BFS的时候，可以通过走反向边来退流。这样我们就无需担心选择增广路的顺序，只要一次BFS能找到增广路，就可以增加流量。
ps.反向边的容量应为0。反向边可以在建图的时候就建立。
5.EK算法：不断BFS直到不存在增广路。单次BFS增广的上界是这条增广路上，一条边还能增加的流量的最小值。找到增广路之后，在正向边上加上流量，在反向边上减去流量。若不存在增广路，则返回已经增加的流量。
ps.为什么根据如上做法，当找不到新的增广路时，就找到了最小割：
以单位边权的图为例，当找不到新的增广路时，我们找到了s到t的m条不相交路径，同时找到了一个大小为m的st割。
对于任意一个割，其大小一定是不相交路径数量的一个上界。所以当已经找到的不相交路径数量等于割容量时，不会再有更小的割。
constexpr int MAXN = 250;
constexpr int INF = 0x3f3f3f3f;
struct Edge {
int from, to, cap, flow;
Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {}
};
struct EK {
int n, m; // n：点数，m：边数
vector<Edge> edges; // edges：所有边的集合
vector<int> G[MAXN]; // G：点 x -> x 的所有边在 edges 中的下标
int a[MAXN], p[MAXN]; // a：点 x -> BFS 过程中最近接近点 x 的边给它的最大流
// p：点 x -> BFS 过程中最近接近点 x 的边
void init(int n) {
for (int i = 0; i < n; i++) G[i].clear();
edges.clear();
}
void AddEdge(int from, int to, int cap) {
edges.push_back(Edge(from, to, cap, 0));
edges.push_back(Edge(to, from, 0, 0));
m = edges.size();
G[from].push_back(m - 2); //G[i]记录和这个节点相关的边的“编号”
G[to].push_back(m - 1);
}
int Maxflow(int s, int t) {
int flow = 0;
for (;;) {
memset(a, 0, sizeof(a));
queue<int> Q;
Q.push(s);
a[s] = INF;//单次BFS中能增广的最大的流
while (!Q.empty()) {
int x = Q.front();
Q.pop();
for (int i = 0; i < G[x].size(); i++) { // 遍历以 x 作为起点的边
Edge& e = edges[G[x][i]];
if (!a[e.to] && e.cap > e.flow) {
p[e.to] = G[x][i]; // G[x][i] 是最近接近点 e.to 的边
a[e.to] =
min(a[x], e.cap - e.flow); // 最近接近点 e.to 的边赋给它的流
Q.push(e.to);
}
}
if (a[t]) break; // 如果汇点接受到了流，就退出 BFS
}
if (!a[t])
break; // 如果汇点没有接受到流，说明源点和汇点不在同一个连通分量上
for (int u = t; u != s;
u = edges[p[u]].from) { // 通过 u 追寻 BFS 过程中 s -> t 的路径
edges[p[u]].flow += a[t]; // 增加路径上边的 flow 值
edges[p[u] ^ 1].flow -= a[t]; // 减小反向路径的 flow 值
}
flow += a[t];
}
return flow;
}
};
dinic算法
1.对残量网络，先BFS分层，得到层次图Gl。
2.在层次图上找到最大的增广流。然后加到原先的流上。
3.重复过程直到不存在增广流。
当前弧优化：如果一个节点u存在大量入边和出边。每次通过一个入边dfs到u点时，如果扫一遍出边表代价非常大。为避免这一缺陷，如果某个时刻我们知道边(u,v)已经增广到极限或v的后侧已经堵塞，我们则没必要再u点dfs流量到v点。据此我们维护u的“还有必要尝试”的第一条边。
dinic算法的dfs函数需要好好理解一下：
class MF{
public:
struct edge{
int v,nxt,cap,flow;//到达的点、边的编号（在e数组的下标）、u点出发的下一条边编号、容量、流量
};
vector<edge> e;
vector<int> fir;//每个点的边的邻接表
int cnt = 0;//有多少条边
int n,S,T;
ll maxflow = 0;
vector<int> dep,cur;//每个点的层数、当前弧指针
MF(){
}
MF(int nn,int SS,int TT):n(nn),S(SS),T(TT){
fir.assign(n+5,-1); cnt = 0;
}
void init(int nn,int SS,int TT){
n = nn,S = SS,T = TT;
fir.assign(n+5,-1); cnt = 0;
}
void addedge(int u,int v,int w){
e.push_back({v,fir[u],w,0});
fir[u] = cnt++;
e.push_back({u,fir[v],0,0});
fir[v] = cnt++;
}
bool bfs(){
queue<int> q;
dep.assign(n+5,0);
dep[S] = 1;
q.push(S);
while(q.size()){
auto u = q.front();
q.pop();
for(int i=fir[u];~i;i=e[i].nxt){
int v = e[i].v;
if(!dep[v] && (e[i].cap > e[i].flow)){//注意是残量网络
dep[v]=dep[u]+1;
q.push(v);
}
}
}
return dep[T];
}
int dfs(int u,int flow){//当前节点在u，传下来的流量为flow
if(u==T || !flow) return flow;//如果u是汇点，或flow为0，则没有必要往下dfs
int ret=0;//当前点能往下成功传的最大流量
for(int &i=cur[u];~i;i=e[i].nxt){//从当前弧开始遍历，随遍历过程不断修改
int v = e[i].v,d;
if((dep[v]==dep[u]+1) && (d = dfs(v,min(flow-ret,e[i].cap-e[i].flow)))){
//必须是下一层的节点，且不堵塞
ret += d;
e[i].flow += d;
e[i^1].flow -= d;
if(ret==flow) return ret;//流量已经传完
}
}
return ret;
}
void dinic(){
while(bfs()){//bfs发现到达不了汇点
cur = fir;//重置当前弧
maxflow += dfs(S,INF);
}
}
}
ISAP算法
从T点向S点bfs。增广还是是从S到T，增广时处理好下轮的层数，因为反向BFS，增广时选择比自己层数少1的点来增广。
增广的过程完成下一轮层数的更新：每次选择出边层数最小的点$j$，然后把自己的层数修改为$d_j+1$。如果没有出边，直接把自己的层数设为n。
容易发现当$d_s\geqslant n$时，不存在增广路，可终止算法
ISAP一样可以当前弧优化。同时还有GAP优化：
记录当前层数i的点的数量num。每当将一个点的层数从x更新到y时，更新num数组的值。若更新后出现$num[x]==0$，说明图出现了断层，一定不存在增广路，可以直接终止算法（实现时直接将$d_s$标记为n）。
jiangly板子 dinic算法
constexpr int inf = 1E9;
template<class T>
struct MaxFlow {
struct _Edge {
int to;
T cap;
_Edge(int to, T cap) : to(to), cap(cap) {}
};
int n;
std::vector<_Edge> e;
std::vector<std::vector<int>> g;
std::vector<int> cur, h;
MaxFlow() {}
MaxFlow(int n) {
init(n);
}
void init(int n) {
this->n = n;
e.clear();
g.assign(n, {});
cur.resize(n);
h.resize(n);
}
bool bfs(int s, int t) {
h.assign(n, -1);
std::queue<int> que;
h[s] = 0;
que.push(s);
while (!que.empty()) {
const int u = que.front();
que.pop();
for (int i : g[u]) {
auto [v, c] = e[i];
if (c > 0 && h[v] == -1) {
h[v] = h[u] + 1;
if (v == t) {
return true;
}
que.push(v);
}
}
}
return false;
}
T dfs(int u, int t, T f) {
if (u == t) {
return f;
}
auto r = f;
for (int &i = cur[u]; i < int(g[u].size()); ++i) {
const int j = g[u][i];
auto [v, c] = e[j];
if (c > 0 && h[v] == h[u] + 1) {
auto a = dfs(v, t, std::min(r, c));
e[j].cap -= a;
e[j ^ 1].cap += a;
r -= a;
if (r == 0) {
return f;
}
}
}
return f - r;
}
void addEdge(int u, int v, T c) {
g[u].push_back(e.size());
e.emplace_back(v, c);
g[v].push_back(e.size());
e.emplace_back(u, 0);
}
T flow(int s, int t) {
T ans = 0;
while (bfs(s, t)) {
cur.assign(n, 0);
ans += dfs(s, t, std::numeric_limits<T>::max());
}
return ans;
}
std::vector<bool> minCut() {
std::vector<bool> c(n);
for (int i = 0; i < n; i++) {
c[i] = (h[i] != -1);
}
return c;
}
struct Edge {
int from;
int to;
T cap;
T flow;
};
std::vector<Edge> edges() {
std::vector<Edge> a;
for (int i = 0; i < e.size(); i += 2) {
Edge x;
x.from = e[i + 1].to;
x.to = e[i].to;
x.cap = e[i].cap + e[i + 1].cap;
x.flow = e[i + 1].cap;
a.push_back(x);
}
return a;
}
};
