简介
所谓网络流,就是给了一张图,有源点和汇点,让你求从源点放水,到汇点的水最多能有多少;
这实际上是一个最大流的问题;
最大流
我们把这张图的每个边看作一条水管,每个水管都有一个容量,那么对于一条从源点到汇点的路径,其最大通过量是这些水管中容量最小的那一个的容量;
对于这个问题,我们有如下的处理方法:
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...
标签:LITTLE,增广,int,网络,long,算法,cnt,dis From: https://www.cnblogs.com/PeppaEvenPig/p/18433017