[算法] A LITTLE 网络流
简介
所谓网络流，就是给了一张图，有源点和汇点，让你求从源点放水，到汇点的水最多能有多少；
这实际上是一个最大流的问题；
最大流
我们把这张图的每个边看作一条水管，每个水管都有一个容量，那么对于一条从源点到汇点的路径，其最大通过量是这些水管中容量最小的那一个的容量；
对于这个问题，我们有如下的处理方法：
EK 算法
定义一条增广路为从源点（设为s）到汇点（设为t）的一条路径，满足其所有边的剩余容量非负；
对于此算法，我们每次都找一条增广路，然后更新每条边的权值直到剩余图中（也即残量网络）没有增广路；
因为我们要重新找增广路，所以还要建反向边，便于回去重新找；
可以看出，它的复杂度瓶颈在边数；
那么最坏情况是每次只能确定一条边，时间复杂度 $ O(nm^2) $，不太适用于稠密图，但实际使用其实达不到此上界；
因为下一个算法使用较普遍，所以这里就不放代码；
Dinic 算法
考虑对于一个残量网络，EK算法会重新遍历整个残量网络，然后只找出一条增广路，考虑将复杂度瓶颈由边转移到点；
于是有了Dinic算法；
首先对图进行分层（就是进行一边BFS，然后将遍历顺序（即深度）相同的点纳入同一层）；
然后每次处理一层的所有点的增广路，直到残量网络不能分层（即s不能到达t）；
我们发现，它和EK的本质区别在于它是以点为单位（每次分层是 $ \Theta(n) $ 的）找增广路，而前者是以边为单位；
时间复杂度： $ O(n^2m) $；
当然，它还有两个优化：当前弧优化和剪枝；
前者是在当前层中只去找能扩展的边，后者是去掉增广完毕的点；
点击查看代码
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
int n, m, s, t;
struct sss{
int t, ne;
long long w;
}e[200005];
int h[200005], cnt;
void add(int u, int v, long long ww) {
e[++cnt].t = v;
e[cnt].ne = h[u];
h[u] = cnt;
e[cnt].w = ww;
}
int now[200005];
long long ans;
int dis[205];
bool bfs() { //点分层；
queue<int> q;
for (int i = 1; i <= n; i++) dis[i] = 0x3f3f3f3f;
q.push(s);
now[s] = h[s];
dis[s] = 0;
while(!q.empty()) {
int tt = q.front();
q.pop();
for (int i = h[tt]; i; i = e[i].ne) {
int u = e[i].t;
if (e[i].w > 0 && dis[u] == 0x3f3f3f3f) {
dis[u] = dis[tt] + 1;
now[u] = h[u];
q.push(u);
if (u == t) return true;
}
}
}
return false;
}
long long dfs(int x, long long sum) {
if (x == t) return sum;
long long k = 0; //当前最小剩余流量；
long long res = 0; //流过点x的总流量；
for (int i = now[x]; i; i = e[i].ne) {
int u = e[i].t;
now[x] = i; //当前弧优化；
if (e[i].w > 0 && (dis[u] == dis[x] + 1)) {
k = dfs(u, min(sum, e[i].w));
if (k == 0) dis[u] = 0x3f3f3f3f; //剪枝；
e[i].w -= k;
e[i ^ 1].w += k;
res += k;
sum -= k; //sum是经过该点的剩余流量；
}
}
return res;
}
void Dinic() {
while(bfs()) {
ans += dfs(s, 0x3f3f3f3f3f3f3f3f);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> s >> t;
int u, v;
long long w;
cnt = 1;
for (int i = 1; i <= m; i++) {
cin >> u >> v >> w;
add(u, v, w);
add(v, u, 0);
}
Dinic();
cout << ans;
return 0;
}
To be continued...