最近花点时间看了看网络流,也深度地学习了一下网络流的各个算法,虽然还有一个没学,但是不影响。

概念引入

首先我们要先理解一下什么是网络,网络与有向图虽然长得一模一样,但是概念略微不一样,首先网络的边权不代表路径长度,代表流量或者花费。

  1. 源点:入读为0的点,只出不进
  2. 汇点:出度为0的点,只进不出

在网络中,对于非源点和汇点的所有点,需要满足流入流量之和等于流出流量之和,中间节点不存储任何流量,任何一条边的流量受限于自己的容量限制。

于是有的人就想要求出:这张网络运作起来的时候,总流量最大能有多少。由于容量限制比较复杂,似乎不容易规划一个最佳方案。

such as:

在这里,很容易得出 $s\to t$ 的最大流量就是2,上面一条路,下面一条路,边上的限制都是1,因此总流量为2。这里我们再给出两个概念:

  1. 增广 :在现有流量基础上发现新的路径,扩大发现的最大流量(注意:增加量不一定是这条路径的流量,而是新的流量与上次流量之差)
  2. 增广路:在现有流量基础上发现的新路径.(快来找茬,和上一条有何不同?)

因此我们有了第一个算法:FF。

虽然一般来说基本通不过测试点,但是还是有必要学的。

FF算法

从源点开始寻找增广路,如过找到那么整条路径的流量减去整个路径上的最小流量,然后重复寻找增广路,直到找不到增广路为止,最大流即是每次增广路减少的流量的和,这个结论是很容易证明的,所以咱就不证了。

很有幸,咱还是写过了这个算法,每次 $\text{dfs}$ 得到一个增广路,这个算法过得了图为树时候的最大流,但是过不去标板,标板的数据量才200个点,还能 TLE 很多点。

但是有一个问题,如果我一开始走了错误的路线,比如上面的图中,假如我走了中间那条路,那么就会导致接下来找不到增广路了,所以我们在走的时候会增加反悔功能,这条反向边就是防止走了错误路线给你反悔用的,假设你走了 $s\to a \to b\to t$ ,那么此时图变成这样:

那么在往下走的过程中我就能经过 $s \to b\to a\to t$,然后到达汇点。中间这条边经过两次,变回一开始的样子,相当于就是没走,这个反向边添加在所有的网络流算法都会用到,因此一定要理解。

这里给出练习这个算法的板子吧——P3931

我写的程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
struct eee{
int next;
int to;
int w;
}edge[maxn<<1];
int r,n,cnt=1,root[maxn],fa[maxn],dest[maxn];
stack<int>path;
inline void add(int x,int y,int w){
edge[++cnt]={root[x],y,w};
root[x]=cnt;
}

void dfs(int u){
for(int i=root[u];i;i=edge[i].next){
int to=edge[i].to;
if(fa[u]==to)continue;
fa[to]=u;
//edge[i^1].w=0;
dfs(to);
}
if(!edge[root[u]].next&&u!=r){
dest[u]=1;
}
}

int find_path(int now,int from,int flow){
if(dest[now])return flow;
int qw=0;
for(int i=root[now];i;i=edge[i].next){
int to=edge[i].to,w=edge[i].w;

//printf("to is %d w is %d\n",to,w);
if(to==from)continue;
if(w==0)continue;
path.push(i);
qw=find_path(to,now,min(flow,w));
if(qw==0)continue;
break;
}
return qw;
}

void maxflow(){
int ans=0;
while(1){

int l=find_path(r,0,0x7fffffff);
if(l!=0&&l!=0x7fffffff){
ans+=l;
while(path.size()){
int e=path.top();
path.pop();
edge[e].w-=l;
edge[e^1].w+=l;
}
}
else{
break;
}
//printf("ans=%d\n",ans);
}
printf("%d\n",ans);
}
int main(){
//freopen("P3931_2.in","r",stdin);
cin>>n>>r;
for(int i=1;i<n;i++){
int x,y,w;
cin>>x>>y>>w;
add(x,y,w);
add(y,x,w);
}
dfs(r);
maxflow();
return 0;
}

这个数据量 $\text{10w}$ 都能过为啥能过呢,据评论区大佬说,因为树是二分图,因此增广路不会超过 $log_2n$ 条,因此这题我这么写能过,但是遇到非树的毒瘤图那真的 $200$ 都能卡住的,而且我下了一下标板的测试点,貌似就是会陷入死循环,我不知道哪里写出来的问题了。

EK算法

在高中的时候我们老师就讲过,在一般情况下,$\text{dfs}$ 一定是没有 $\text{bfs}$ 优的。因此我们每次都挑一个看上去路径最短的增广路,既然要求最短了我们就可以用 $\text{bfs}$ 去寻找增广路了。

EK算法可以通过标板——P3376

我写的程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<bits/stdc++.h>
#define int long long
#define maxn 500
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
struct eee{
int to;
int w;
int next;
}edge[5005<<1];
struct ee{
int v;
int edge;
}pre[5005<<1];

int root[maxn],inque[maxn],cnt=1;
int n,m,s,t;
inline void add(int x,int y,int w){
edge[++cnt]={y,w,root[x]};
root[x]=cnt;
}
bool bfs(){
queue<int>q;
memset(inque,0,sizeof(inque));
memset(pre,0xff,sizeof(pre));
inque[s]=1;
q.push(s);
while(q.size()){
int u=q.front();
q.pop();
for(int i=root[u];i;i=edge[i].next){
int v=edge[i].to;
if(!inque[v]&&edge[i].w){
pre[v]={u,i};
if(v==t){
return 1;
}
inque[v]=1;
q.push(v);
}
}

}
return 0;
}
void EK(){
long long ans=0;
//printf("%lld\n",sizeof(ans));
while(bfs()){
long long mi=inf;
for(int i=t;i!=s;i=pre[i].v){
mi=min(mi,edge[pre[i].edge].w);
}
for(int i=t;i!=s;i=pre[i].v){
edge[pre[i].edge].w-=mi;
edge[pre[i].edge^1].w+=mi;
}
ans+=mi;

}
printf("%lld\n",ans);
}

void sync(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}

signed main(){
//freopen("P3376_7.in","r",stdin);
sync();
cin>>n>>m>>s>>t;
while(m--){
int x,y,w;
cin>>x>>y>>w;
add(x,y,w);
add(y,x,0);
}
EK();
return 0;
}

Dinic算法

EK算法虽然比较优了,但是有一个情况还是比较费时的,如下图所示

假设我 $S\to A$ 再经过更多的点,$A$ 后面的分支更多,那么每一次都要 $\text{bfs}$ 开销也是很大的的,重要的是很多路我们会重复遍历。这里就体现出了 $\text{Dinic}$ 算法的优了。

它只需要开始一次 $\text{bfs}$ 就能处理多条路径,它的思想是这样的:先对网络进行 $\text{bfs}$ 分层,我只找这样的增广路:

对于路径上任意 $u\to v$ 的边,都有 $v$ 在 $u$ 的下一层。我一次可以处理多条增广路,如果没有增广路那么我将对网络重新分层,直到 $\text{bfs}$ 无法遍历到汇点时。

标程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>
#define int long long
#define maxn 505
#define maxe 5005
using namespace std;
struct eee{
int to;
int w;
int next;
}edge[maxe<<2];
int root[maxn],dep[maxn],cnt=1,s,t,n,m,ans;
queue<int>q;
inline void add(int x,int y,int w){
edge[++cnt]={y,w,root[x]};
root[x]=cnt;
}
//网络分层
bool bfs(){
//puts("1");
while(q.size())q.pop();
q.push(s);
memset(dep,0,sizeof(dep));
dep[s]=1;
while(q.size()){
int u=q.front();
q.pop();
for(int i=root[u];i;i=edge[i].next){
int v=edge[i].to,w=edge[i].w;
if(!dep[v]&&w){
dep[v]=dep[u]+1;
q.push(v);

}
}
}
return dep[t];
}
//从u出发,目前已有in的流量
int dfs(int u,int in){
if(u==t)return in;
int ans=0;
for(int i=root[u];i;i=edge[i].next){
int v=edge[i].to,w=edge[i].w;
if(dep[v]==dep[u]+1&&w){
int res=dfs(v,min(in,w));
edge[i].w-=res;
edge[i^1].w+=res;
in-=res;
ans+=res;
}

}
if(ans==0)dep[u]=0;
return ans;
}

void sync(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}

signed main(){
sync();
cin>>n>>m>>s>>t;
while(m--){
int x,y,w;
cin>>x>>y>>w;
add(x,y,w);
add(y,x,0);
}
int ans=0;
while(bfs()){
ans+=dfs(s,0x7fffffffffffffff);
}
cout<<ans<<endl;
}

又一个板子收入囊中,网络流应该会 $\text{Dcini}$ 差不多了吧qwq。