同步发表于 P5192 题解。
1. 知识储备
网络流 + 最大流。
(如果各位 dalao 已经滚瓜烂熟,请跳过)。
1. 网络流
通俗的讲,网络流就是一个水系,有源点(水库, S )和汇点(大海, T ),中间有很多节点,中间的节点不储存流,作为一个中转站。
每一条边有一个容量(河道宽度),也有一个流量。显然流量小于等于容量。
如图是一张网络流。

已经有流量的图被称为残留网络。
注意:残留网络中,有反向边,而一般认为原图中没有反向边。
反向边的容量是正向边的流量。
(可以这么认为,反向边是用来退回正向边的流量,而最多就退回原来流过的量)
刚才那张图的残留网络是如下:

增广路:沿着容量大于0的边,从 S 到达 T 的路径,
(这么多已经足够,详细解释请见百度 逃 )
2. 最大流
我们现在想要求从源点到汇点能流的最大值。
显然,上面的那张图不是最大流。
最大流应该是这样。

3. Edmonds-Karp 与 Dinic ——求最大流的算法
Edmonds-Karp 的主要思路是每次寻找一条增广路。
原理可以理解为搜索,直到流不过去为止。
Code:
1 |
|
Dinic 是 EK 的优化,主要思想是建立分层图,一次找多个增广路
Code:
1 | queue <int> q; |
2. 无源汇上下界最大流
我们当然希望他不要有上下界,所以要转化成普通的最大流。
设边 (u,v) 流量为 f(u,v), 那么有
可以得到:
可以发现,我们直接从 u 连一条 cmax(u,v) - cmin(u,v) 为容量的边即可!
真的可以了吗?(雾)
回顾原来的定义,每一个节点都是要不储存流量的,但这样的话,会导致节点 u 存储的一些流量,为
为了弥补这一缺陷,我们不得不建立一个源点和汇点(其他点无法在流入或流出)
如果该项大于 0 ,我们就从源点连一条边到该点,否则就从该点流出到汇点(别无选择)
于是,我们就可以用最大流了。
还有一个问题,假设从源点不能每一条边都是满流?此时,我们可以发现,如果不是满流,每一个点还是要储存流量,就会导致性质无法满足。
最后的最大流,就是从源点出发的流加上每一条边原来没有计算的流量。
(可以先理解,因为每一个流都会从源点流出,不然就会有其他点不流量守恒了)
Code: 略(主要是不想打)
3. 有源汇上下界最大流
有源汇对于无源汇来说,有一点不同:原来的源点(记为 s )和汇点(记为 t )也是不流量守恒的。
显而易见的方法是,从 t 到 s 连一条
然后就先从 S 到 T 用 Dinic ,再 s 到 t 用 Dinic 。
两次的流量相加,就可以了。(就可以了)
但真的可以吗?(雾)
是可以的(不要被我问一次就犹豫了)
但是我这里需要严谨证明一下。(看不懂可以略过)
证明
我们需要证明的是原图中从 s 到 t 的可行流与新图第一次 Dinic 后从 s 到 t 的可行流是一 一对应的。
首先,原图的可行流与新图中的满流是一一对应的。
1. 原图至新图
假设新图有一个满流 f(S,T) ,对于任意一个原图的可行流,即一个新图的满流,相减后, S 和 T 相关的边,流量都会变成 0 。
又由于有 c(t,s)=
2. 新图至原图
设新图中有一个满流 f(S,T) ,并有任意一个 s 到 t 的可行流 f(s,t).
那么,f(S,T)+f(s,t) 也一定是一个满流,同时由于 f(s,t) 不经过 S 和 T ,每个点也满足流量守恒。
所以对任意一个 f(s,t) ,都有一个满流与之对应,也就是有原图的可行流。
证毕!
4.回归本题
由标题可以看出,本题是一个模板题。
- 先建立一个源点。
- 从源点到每个少女,流量为 [gi,
) 从每个少女到每一天,流量为 [li,ri]
从每一天到汇点,流量为 [0,di]
记得清零,以及少女的编号问题。
最后,献上代码。其它问题看注释,或者私信。
Code:
1 |
|
Gitalking ...