网络最大流
EK
Dinic+当前弧+剪枝
Dinic：BFS分层，每次只向下一层流
当前弧：流完的边删掉
剪枝：流完的点删掉
细节
\(\textcolor{red}{*}\)加反边时反边容量为0，价值取反，不要搞混了（已经搞错3次了）
剪枝优化尽量不用，如果一定要用的话，注意\(u\to v\)边权为\(0\)不要操作（调用DFS和dis[v]=INF），亲测会死循环
费用流（最小权最大流）
EK+SPFA
在残量网络中找一条增广路，使得该增广路单位费用最小
即把最大流的\(EK\)算法中随便找一条路变成找一条最短路
Dinic+PD+dijkstra
人话：用Johnson算法的方法处理负权边（原始对偶算法），然后跑dij，在最短路DAG上跑Dinic
在边权较小时优势尤为明显
细节
不需要再次BFS分层，直接根据dis[v]==dis[x]+e[i].dis转移即可
与普通Dinic不同的地方：需要加vis[]打标记，防止进入环（为什么进环会死循环？
核心代码
int Dfs(int x,int sum) {
if(x==t) return sum;
int fl=0;
vis[x]=1;
for(int i=rad[x];i;i=e[i].next) {
int v=e[i].to;
rad[x]=i;
if(dis[v]==dis[x]+e[i].c&&e[i].w&&!vis[v]) {
int tp=Dfs(v,min(sum,e[i].w));
fl+=tp; sum-=tp; ansc+=tp*e[i].c;
e[i].w-=tp; e[i^1].w+=tp;
if(!sum) break;
}
}
vis[x]=0;
return fl;
}
费用流的凸性
最小费用可行流
题目
P5814 [CTSC2001] 终极情报网
题意有点小问题，但是其实是简单费用流
取\(log\)化乘为加即可
p.s. 在松弛时，边权的判断要变成\(dis[v]+eps<dis[x]+e[i].w\)，否则说是会把\(0\)环判成负环一直跑（why）
模拟费用流
上下界网络流
无源汇上下界可行流
考虑转化为一般的网络流问题（即消除下界），考虑直接先把每条边的流量下界流走，限制转换成\([0,R_i-L_i]\)。但此时点的流量不守恒，考虑用源汇点调整
对于多余/亏欠的流量，向\(S/T\)连权值为\(|W_i|\)边（这里的理解是，这些流量本不应存在，相当于我们为这些流量找了一个“借口”，即从源点来的/到汇点去的，使得这个流合理地存在，而不是理解为“拿源点的流量把它填到0”），此时跑最大流（易知S,T连边的流量相同），如果满流，则调整合法，流量守恒
有源汇上下界可行流
源汇点流量不守恒，但是如果把源汇点“合并”，那这个点就满足流量守恒
做法是连一条\((T,S,0,INF)\)的边，使\(T\)的出流来到\(S\)，然后就可以跑无源汇上下界可行流了
有源汇上下界最大流
考虑可行流，满足所有流图的限制，但是会有边没跑满
直接在可行流的基础上，在原图的残量网络上跑最大流即可
p.s. 可以直接简单修改可行流跑的图（改源汇，删\(T\to S\)），不必手动还原（如何还原？）