前言
由于网络流极其庞大而资料有限，我决定用这个博客先记录一下我学习的大纲，在后期有可能补上内容。对于网上可以找到的，我就一笔带过，只是说明应该了解这个东西；而对于网上难以找到的一些资料，我会尽我所能写出来。
大纲
- 基本概念
- 网络最大流 - 增广路类
- 最大流最小割定理：内容与证明
- Ford - Fulkerson：从贪心上简单地 支持反悔 的实现（增加反边容量）
- Edmonds - Karp（\(O(nm^2)\)）：从 F-F 到 EK 的优化，最短路不减 引理（BFS 寻找最短增广路）
- dinic（\(O(n^2 m)\)）：当前弧优化，整体 增广过程 的把握（多路增广）
- ISAP：单次 BFS 与 GAP（尤其是实现时
if(!ans) return flow;阻止优化后的 dep 修改机制影响正确性） - F-F \(\to\) EK \(\to\) dinic \(\to\) ISAP，其实是一个不断迭代优化的过程，贪心反悔贯穿始终。
- 时间复杂度证明：反证法 和 极限思想 的极致体现
dinic 复杂度证明（名字自己起的，内容自己证的，建议作为 OI-wiki 食用辅料）
单次多路增广上界：\(O(nm)\)
层次图层次严格单增证明：
- 合法延续性：原图或前代层次图的 高度标号 / 层次 在 多次迭代 后仍然 合法
合法：任意两点的高度标号 / 层次 大小关系不变；- 同长同层性：长度相同 的增广路的 对应节点 的 层次相同;
\(\implies\) 这两条增广路在 同一层次图 上；- 单次消失性：对 同一层次图 的任意增广路，必然有一条在增广路中的边在下一代残量网络中消失。
故可证，每次迭代后的层次图严格单调递增。
关于 ISAP 你想要的
OI-wiki 的代码好像有问题，此外他本身也比较复杂，可以考虑使用如下代码。
\(\text{AC Code by ISAP with the current arc, gap and dep optimization, } 47 ms\text{ without O2.}\)
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fsp(x) std::fixed<<std::setprecision(x)
#define forE(u) for(int p=head[u],v=to[p];p;p=next[p],v=to[p])
const int N=205,M=5005;
int n,m,s,t;
struct flow_network {
int cnt=1,head[N],to[M<<1],next[M<<1],lim[M<<1];
int dep[N],gap[N];
inline void add(int u,int v,int w) {
to[++cnt]=v,lim[cnt]=w,next[cnt]=head[u],head[u]=cnt;
to[++cnt]=u,lim[cnt]=0,next[cnt]=head[v],head[v]=cnt;
}
int cur[N];
ll dfs(int u,ll ans) {
if(u==t) return ans;
ll flow=0;
for(int &p=cur[u];p&&ans;p=next[p]) {
int c=std::min(ans,(ll)lim[p]),v=to[p];
if(dep[v]==dep[u]-1&&c) { int fl=dfs(v,c); flow+=fl,ans-=fl,lim[p^1]+=fl,lim[p]-=fl; }
if(!ans) return flow;
}
if(--gap[dep[u]]==0) dep[s]=n;
++gap[++dep[u]];
return flow;
}
inline ll max_flow(int s,int t) {
ll flow=0; std::queue<int> q;
memset(dep,-1,sizeof dep);
q.push(t),gap[dep[t]=0]=1;
while(!q.empty()) {
int u=q.front(); q.pop();
forE(u) if(!lim[p] && dep[v]==-1) ++gap[dep[v]=dep[u]+1],q.push(v);
}
while(dep[s]<n) { memcpy(cur,head,sizeof head); flow+=dfs(s,1e18); }
return flow;
}
} f_n;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr); std::cout.tie(nullptr);
std::cin>>n>>m>>s>>t;
for(int i=1,u,v,w;i<=m;++i) { std::cin>>u>>v>>w; f_n.add(u,v,w); }
std::cout<<f_n.max_flow(s,t)<<'\n';
return 0;
}
优化后的 ISAP 深度维护机制正确性证明
考虑采用数学归纳法。首先，我们先了解该机制的运行细节。
引理 1. 在多路增广中，增广路中阻塞流靠近源点一侧的节点 \(u\) 到源点 \(T\) 的路径上的所有节点深度不改变。
考虑我们多路增广的过程
ll dfs(int u,ll ans)，dfs 的第二个传参ans表示阻塞流的大小。所以从 \(u\) 到 \(T\) 的路径的 \(ans\) 必然被流光，即 \(ans=0.\) 根据if(!ans) return flow;必然直接返回，不改变深度。该引理得证。接下来，我们分情况证明其正确性。
结论 2. 对于再无法提供贡献的节点，深度增加与深度赋值极大值等效。
考虑为无法贡献节点赋值极大值（一般是 \(n\)）的目的：使其无法再遍历。深度增加会使这些节点组成路径最终与汇点无法通过判断语句
dep[v]==dep[u]-1，进行联结，故深度增加与深度赋值极大值等效，该结论得证。但要注意的是，这种写法会导致这些节点在接下来的遍历过程中仍然被访问，（但无法抵达 \(T\)，没有贡献。）会增加一些复杂度，但整体影响不大。该深度维护机制在整体上对代码书写与运行速度的提升都是正向的。结论 3. 对于还能继续产生贡献的节点，深度增加可以保证其所有边的贡献全部被计入。
我们以 源点 \(S\)（和 dinic 相同，和 ISAP 相反）为中心建立层次图，\(dis(u)\) 表示节点 \(u\) 的层次，将所有边大致分为以下几类：
- 返祖边：前往 \(dis(v)<dis(u)\) 的节点 \(v\) 的边；
- 横叉边：前往 \(dis(v)=dis(u)\) 的节点 \(v\) 的边；
- 合法边：前往 \(dis(v)=dis(u)+1\) 的节点 \(v\) 的边；
- 前向边：前往 \(dis(v)>dis(u)+1\) 的节点 \(v\) 的边。
接下来我们分别证明这些边的贡献会被计入。
- 返祖边：若该返祖边有贡献，则在该边提供贡献前 \(S\) 必然可达 \(u\) 且不可达 \(v\)（若可达 \(v\) 则该边仍不合法），此前必然存在阻塞流位于 \(u \to T\) 一段使 \(u\) 的深度增加，或位于 \(S \to v\) 一段使 \(v\) 的深度保持不变，直至 \(dis(v)=dis(u),\) 该边成为横叉边。
- 横叉边：若该横叉边有贡献，则在该边提供贡献前 \(S\) 必然可达 \(u\) 且不可达 \(v,\) 此前至少存在一条阻塞流位于 \(u \to T\) 一段使 \(u\) 的深度增加，并存在阻塞流位于 \(S \to v\) 一段使 \(v\) 的深度保持不变，随后 \(dis(u)=dis(v)+1,\) 该边成为合法边。
- 合法边：若此次阻塞流不在边 \((u,v)\) 上，则 \(u,v\) 的深度同时增加，该边仍然合法，有机会在后续的遍历中继续被增广。
- 前向边：考虑前向边的定义，必然在最初有 \(dis(v) \leq dis(u)+1,\) 则该边若有贡献，必然在此代层次图前已经被计入。
综上，所有边的类型都会被计入，该结论得证。
根据结论 2 和结论 3，当前深度维护机制的正确性得以证明。
- 网络最大流 - 预留推进类：准备鸽了……学完其他的再学，一般用不上 qwq
- 无负环费用流
- 基于 EK 的 SSP：如何 结合 EK 和 SPFA，正确性证明
- 基于 dinic 的 SSP：如何 写出正确的代码，注意 dfs 错误可能导致 爆栈空间
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fsp(x) std::fixed<<std::setprecision(x)
#define forE(u) for(int p=head[u],v=to[p];p;p=next[p],v=to[p])
const int N=5e3+3,M=5e4+4;
struct network {
int cnt=1,head[N],to[M<<1],next[M<<1],lim[M<<1],cst[M<<1];
inline void add(int u,int v,int w,int c) {
to[++cnt]=v,lim[cnt]=w,cst[cnt]=c,next[cnt]=head[u],head[u]=cnt;
to[++cnt]=u,lim[cnt]=0,cst[cnt]=-c,next[cnt]=head[v],head[v]=cnt;
}
int t,cost=0,cur[N],dis[N],in[N];
int dfs(int u,int res) {
if(u==t) return res;
int flow=0; in[u]=1;
for(int p=cur[u];p&&res;p=next[p]) {
cur[u]=p;
int c=std::min(lim[p],res),v=to[p];
if(dis[u]+cst[p]==dis[v]&&c&&!in[v]) { int fl=dfs(v,c); flow+=fl,res-=fl,cost+=cst[p]*fl,lim[p]-=fl,lim[p^1]+=fl; }
}
if(!flow) dis[u]=-1;
return in[u]=0,flow;
}
std::pair<int,int> mincost(int s,int t) {
int flow=0; this->t=t;
while(1) {
std::queue<int> q;
memcpy(cur,head,sizeof head);
memset(dis,0x3f,sizeof dis);
dis[s]=0,in[s]=1,q.push(s);
while(!q.empty()) {
int u=q.front(); in[u]=0,q.pop();
forE(u) if(lim[p]&&dis[v]>dis[u]+cst[p]) {
dis[v]=dis[u]+cst[p];
if(!in[v]) in[v]=1,q.push(v);
}
}
if(dis[t]>1e9) return {flow,cost};
flow+=dfs(s,1e9);
}
}
} ntw;
int n,m,s,t;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr); std::cout.tie(nullptr);
std::cin>>n>>m>>s>>t;
for(int i=1,u,v,w,c;i<=m;++i) { std::cin>>u>>v>>w>>c; ntw.add(u,v,w,c); }
auto ret=ntw.mincost(s,t);
std::cout<<ret.first<<' '<<ret.second<<'\n';
return 0;
}