网络流 最大流算法
网络
图论中的网络是一种特殊的有向图，与有向图不同的是网络存在容量、源点和汇点
- \(E\) 边集中的每一条边 \((u,v)\) 都有一个被称为容量的权值 \(c\)
- \(V\) 点集中存在两个特殊点：源点 \(s\) 和汇点 \(t\)
在网络 \(G=(V,E)\) 中，流是一个从边集到整数集的一个函数，\(f(u,v)\) 表示边 \((u,v)\) 上的流量，\(c(u,v)-f(u,v)\) 表示这条边的剩余容量
在网络中，合法的可行的流应该满足性质：
- 容量限制：\(0\le f(u,v)\le c(u,v)\)
- 流量守恒：$\sum\limits_{(u,x)\in E} f(u,x)=\sum\limits_{(x,v)\in E} f(x,v),x\ne {s,t} $ ，形象化的说，一个普通点流入的容量等于流出的容量
最大流问题
我们希望在网络 \(G=(V,E)\) 中找到合适的流 \(f\) ，最大化这个网络的流量 \(\lvert f\rvert =\sum\limits_{x\in V}f(s,x)-\sum\limits_{x\in V}f(x,s)\)
增广路： 一条从源点到汇点的路径，路径上所有边的剩余容量都大于 \(0\)
残留网： 网络中所有结点和剩余容量大于 \(0\) 的所有边构成的子图
EK算法
在建图时给每个有向边都构建一条反向边，容量为 \(0\) ，目的是提供一条退流的路径，一旦前方的增广路无法连通可行流，那么就可以通过退流管道将增广路的部分流量退回
因为需要快速的定位反向边，所以采用链式前向星的方式存图
struct edge{int v; LL c; int ne;};
edge e[M];
int h[210], idx = 1;//从2开始给边进行编号，0是哨兵void add(int u, int v, LL c){e[++idx] = {v, c, h[u]};h[u] = idx;
}for (int i = 1; i <= m; i++){int u, v;LL c;cin >> u >> v >> c;add(u, v, c);add(v, u, 0);
}
通过 BFS 找到一条增广路
类似贪心的扩展，每次只走到一个没有被访问过的节点
int pre[210];//记录节点的前驱边
LL mf[210];//s到该点的流量上限bool bfs(void){memset(mf, 0, sizeof mf);queue<int> q;q.push(s);mf[s] = 1e9;while (q.size()){int u = q.front();q.pop();for (int i = h[u]; i; i = e[i].ne){//枚举所有出边int v = e[i].v;if (mf[v] == 0 && e[i].c){//只有这个邻点没有被访问过且有容量mf[v] = min(mf[u], e[i].c);pre[v] = i;q.push(v);if (v == t) return 1;//能走到汇点}}}return 0;//不能走到汇点，说明无可行流
}
每轮 BFS 都找到一条可行流，累加这些流的流量，然后构建残留网
LL EK(void){LL flow = 0;while (bfs()){//存在可行流时int v=t;//从汇点出发while (v != s){//回溯到源点int i = pre[v];e[i].c -= mf[t];e[i^1].c += mf[t];//更新退流管道v = e[i^1].v;//走反向边}flow += mf[t];}return flow;//返回最大流
}
总的时间复杂度上界为 \(O(nm^2)\) 的级别，\(n,m\) 分别为点数和边数，实际上会比这快得多
Dinic算法
区别于 EK 算法每一轮只累加一条增广路的流量，我们可以先将点 BFS 分层然后通过 DFS 寻找多条增广路
LL dfs(int u, LL mf){if (u == t) return mf;//如果到终点，返回流量LL res = 0;for (int i = cur[u]; i; i = e[i].ne){cur[u] = i;//当前弧优化int v = e[i].v;if (dep[v] == dep[u] + 1 && e[i].w){//只有当下一个节点是下一层时才搜索LL f = dfs(v, min(mf, e[i].w));//流量限制e[i].w -= f;e[i ^ 1].w += f;//退流res += f;//累加当前流量mf -= f;if (mf == 0) break;//如果当前节点以及没有流量就立即返回}}if (res == 0) dep[u] = 0;//残枝优化return res;
}
其中的当前弧 cur[u] 表示节点 \(u\) 在链式前向星中已经考虑过了哪些边，再次进入循环时就可以跳过这些边
残枝优化的意义时，如果当前节点的 res 为 \(0\) ，这个节点就不会连通到汇点，所以在当前的残留网中就不需要考虑了
LL dinic(){LL flow = 0;while (bfs()){memcpy(cur, h, sizeof h);//重置当前弧flow += dfs(s, 1e9);//累加可行流}return flow;
}
时间复杂度为 \(O(n^2m)\) 级别，在稠密图中的运行效率很优