前言:
花了一礼拜学了网络流,最小割及费用流,估计还要再花半个月把整个网络流彻彻底底地过一遍。
这篇博文先记一下学网络流全家桶中各代码的一些总体思路&细节,再挑十几道题讲讲如何正确建图(可能还不够)。
现在是$19/03/07$,时间不够,今晚就总结下几个板子吧。。
网络流入门
概念啥的别类比水流,太抽象,类比人流会好理解一些(认真)
引入新的概念:增广路。和二分图来回走交替路不同,网络流的增广路就是一条最大容量>实际流量的路径,找出所有增广路之后就可以得到最大流。
为啥是严格大于的呢,因为如果实际容量已经等于最大容量了,就相当于你这时候已经再也挤不下人了,如果你还认为可以加0个人就会死循环, $if (!v[u]$&&$w)$ 的$w$就体现这一点(意思是仍有容量)。。
- 对于每次增广路的处理就类似二分图了,核心思想都在于反悔,只不过二分图是递归回去找错误,EK是把错误以反向边的形式记录下来,要是想反悔直接送您回家
反向边虽然是我们脑补出来的,但是也是要一开始建在图里面,实打实参加求增广路过程的。。
反向边w初值为0,在EK算法中关于正常边反着操作就行了。
$1.~EK$算法:
找增广路实质上还是BFS暴力搜索的过程(要注意的都在代码里注释了):
1
2
3
4
5if (!v[u]&&w) {//没访问过+还有流量=走着
p[u].pp=k,p[u].ed=i;
if (u==t) return 1; //流到终点就是增广路!
v[u]=1; q.push(u);
}找完增广路我们也顺手把路径存下来了,然后依然是暴力走增广路的操作:
①先暴力走一遍增广路找最小流量
②再暴力修改所有增广路边权和反向边边权
③答案加上。1
2
3
4
5
6
7
8for (int i=t;i!=s;i=p[i].pp) mw=min(mw,e[p[i].ed].w);
//找这条路的最小流量,减掉!
for (int i=t;i!=s;i=p[i].pp){
int ed=p[i].ed;
e[ed].w-=mw,e[ed+1].w+=mw;
}
//从终点倒回去找前驱,反向边的处理
ans+=mw;
EK部分代码务必要在5分钟内打完+正确,切忌将时间浪费在这上面!!
1 |
|
$2.~Dinic$算法
$1.~ $概念:
EK每次搜到一条增广路就要重新bfs下,太慢啦!
我们要搞一个可以一次多条增广路一起更新的算法,于是就又发明了dinic。
$2.~ $核心思想:
引入分层图的概念,把不同点到起点的最短距离用BFS求出,然后用DFS每次都找当前深度+1的点,往下推进,回溯的时候就顺便更新所有增广路上的点。
$BFS,DFS的时候依然要遵循有流量再走的原则(说白了就还要判$w>0$),是否访问到改成判断最小深度,将访问的v数组挪到里面处理入队列之类的问题。。
最后通过判断终点深度是否是INF,来确定是否还有增广路。
DFS每次找到深度加一的点后,递归应该这样写:1
2
3
4
5
6
7
8
9int mw=0;
if (p==n) return now;
...
if (w&&d[u]==d[p]+1){ //这里也要判断流量,不然死循
if (mw=dfs(u,min(now,w))) {
e[i].w-=mw,e[i^1].w+=mw;
return mw;
//找着增广路了,直接回【就太慢了】。
}
now是递归里上一次的最大流量,但发现这依然是DFS一下BFS一下,还是慢。。
$3.~$Dinic优化:
于是就有了多路增广优化!
- 核心思想:只要我当前点流出的流量小于我的最大流入流量,我就能一直找增广路!
设一个变量used表示当前节点已经用了多少流量,那么只要加一行就会极大优化时间:1
2
3
4
5
6
7
8if (w&&d[u]==d[p]+1){ //这里也要判断流量,不然死循
if (mw=dfs(u,min(now-used,w))) {
//由于当前流量已经用了一点,不在是最大流量了,所以要更新。
e[i].w-=mw,e[i^1].w+=mw;
used+=mw; if (used==now) break;
//找着增广路了,直接回【就太慢了】。
}
}
其实已经挺快了,但是那些人闲着无聊又发明了弧优化。
- 核心思想:当我们增广完一条边,退出这条边递归后,这条边就没有利用价值了,因为它所经过的增广路径已经被榨干了。。
于是我们就搞一个c数组来代替fir数组,直接从上一个没有被榨干的边再走,之前那些边就跳过了。
如图,比方说先走s->3->t,那么3->t这边就废了,当我们再从s->1->3时候,我们就直接到3->5,不管t了。。
写出来大概是:
- BFS里面 $memcpy(c,fir,sizeof(fir));$
- DFS:
1
2
3
4for (int i=c[p];i;i=e[i].next)
{
c[p]=i;
....
大概就这样??
代码依然保证不超过6~7分钟打完加正确: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
using namespace std;
struct ed{
int u,next,w;
}e[300000];
struct path{
int pre,ed;
}p[300000];
int n,m,s,t,x,y,w,ans,st=1,c[100000],fir[100000];
int d[100000]; queue<int> q; bool v[100000];
void add(int u,int v,int w){
e[++st].u=v; e[st].next=fir[u]; e[fir[u]=st].w=w;
}
bool bfs()
{
for (int i=1;i<=n;i++) v[i]=0,d[i]=INT_MAX/2,c[i]=fir[i];
q.push(s); v[s]=1; d[s]=0;
while (!q.empty())
{
int k=q.front(); q.pop();
for (int i=fir[k];i;i=e[i].next)
{
int u=e[i].u,w=e[i].w;
if (d[u]>d[k]+1&&w)
{
d[u]=d[k]+1;
if (!v[u]) v[u]=1,q.push(u);
}
}
}
return (d[t]<INT_MAX/2);
}
int dfs(int p,int now)
{
if (p==t) return now;
int mw=0,used=0;
for (int i=c[p];i;i=e[i].next)
{
c[p]=i;
int u=e[i].u,w=e[i].w;
if (w&&d[u]==d[p]+1)
//这里也要判断流量,不然死循
{
if (mw=dfs(u,min(w,now-used)))
{
e[i].w-=mw; e[i^1].w+=mw; used+=mw;
if (used==now) break;
}
}
}
return used;
}
int dinic()
{
while (bfs())
{
ans+=dfs(s,INT_MAX/2);
}
return ans;
}
int main()
{
cin>>n>>m>>s>>t;
for (int i=1;i<=m;i++) {
cin>>x>>y>>w; add(x,y,w); add(y,x,0);
}
cout<<dinic()<<endl;
}
$3.~ $最大流最小割
直接摘抄笔记了。
费用流问题
简单题意: 询问最大流的同时给每条边加一个边权,表示当前边的单位流量费用,询问最小花费。
对于最大流简单修改:
$~1.~$对于建边:
每次多加一个费用F,表示这条边的边权。对于反向边的话边权为-F,类比人流可以当做退款。
当然也可以类似求最大费用问题。只要通过将正边权变负,负边权变正再跑最小费用,取个绝对值就行啦!
$~2.~$对于EK算法:
只需跑关于费用F的最短路即可。
因为如果你没有增广路了,你肯定就到不了终点,这里仍可用$d[t]<INF$判断;如果你有增广路,你肯定要优先选一条总费用最小的,于是跑最短路,使$\sum_s^t c[i]$最小即可。
而且有细节要注意的是,这里的所有操作均和SPFA相同,尤其是入队出队之类的,EK本来是有向图而且是找单向流所以不要再标记$v[k]=0$,但SPFA要;顺便这里的权值是F,不是W,不要再打错了$QwQ$!
$~3.~ $对于Dinic算法:
由于EK费用流本质上还是找一条增广路处理一条增广路,效率照样低。我们当然还是想用Dinic多路增广的方式来提高效率,但具体应该怎么操作呢?
于是上古神犇zkw在发明主席树后又搞出了SPFA+dinic的费用流,太强辣%%%!
大体上就是把分层图的d[u]=d[k]+1
改成加d[u]=d[k]+f
(这部分和EK一样的);同样在以Dinic的方式dfs里找增广路,而且仍可多路增广及弧优化!
对于dfs中的细节,由于这次分层方式是费用,所以会出现f=0
的情况,所以只能通过访问标记的方法来规避死循了。。
具体来说就是将原来的DFS:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17ll dfs(ll p,ll now)
{
if (p==t) return now;
ll used=0,mw=0;
for (int i=c[p];i;i=e[i].next)
{
c[p]=i;
ll u=e[i].u,w=e[i].w;
if (w&&d[u]==d[p]+1)
if (mw=dfs(u,min(now-used,w)))
{
e[i].w-=mw; e[i^1].w+=mw;
used+=mw; if (used==now) break;
}
}
return used;
}
改成现在这样(已注释):1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22int dfs(int p,int now)
{
if (p==t) {
v[t]=1; ans+=now; return now; //找到终点就顺手记下流量了。。
}
int mw=0,used=0; v[p]=1; //标记此点已访问
for (int i=c[p];i;i=e[i].next)
{
c[p]=i;
int u=e[i].u,w=e[i].f;
if ((!v[u]||u==t)&&e[i].w&&d[u]==d[p]+w)
//因为终点被标记了依然可以流过去
{
mw=dfs(u,min(e[i].w,now-used));
if (mw) {
cost+=w*mw; e[i].w-=mw; e[i^1].w+=mw;
used+=mw; if (now==used) break;
}
}
}
return used;
}
上下界费用流
咕咕,等做了那种题顺便再学吧。。
然后板子啥的就没了。。去做题吧!