RainAir
My OI Blog
RainAir
最小割模型

网络流题目中,如果一种物品有两种状态(选或不选),告诉你每一种状态产生的收益/代价,我们就可以通过使用最小割模型来解决这个问题。但是如果物品的状态扩展到了 $k$ 种,我们就需要用一种新的建图方法。
我们拿两道题目举例:

RatingProgressAward

*TCO2017 Semifinal
题目链接
如果对于积分做了前缀和之后我们发现题目就是要求在满足限制的条件下最大化区间和。
对于一个点 如果我们知道了答案区间在哪 我们可以有三种状态:在答案区间左边,在大安区间内,在答案区间右边。这就是三种状态了。
我们发现在同一区间内 他们的顺序我们是不需要考虑的(内部顺序可以自己排),我们只需要考虑区间与区间的点是否满足拓扑图的要求。
首先对于每个点的三种状态,设积分为 $w$,我们设计出这样的网络:
https://blog.aor.sd.cn/wp-content/uploads/2019/08/QQ20190801-231541.png
如果割掉左边的边就会选择状态 1,后面同理。我们发现这个网络流就十分符合我们题目的要求。
然后我们考虑如何对点和点之间的限制。如果有一对限制 $(u,v)$ 表示 $u$ 要在前面,我们发现我们其实是不希望在第 $u$ 行上的割边在 $v$ 后面。所以我们只需要通过连容量为 $+\infty$ 的边来强制不能出现不符题意的情况即可。
建图大概如下:
https://blog.aor.sd.cn/wp-content/uploads/2019/08/QQ20190801-231842.png
于是这个题目就可以愉快的写出代码了:

FoxAndCity

*SRM590
题目链接
我们观察加入边之后的 $dis$ 数组,发现它需要满足以下条件:
1. $dis_1 = 0,dis_i \neq 0(i \geq 2)$
2. 对于原图中的边 $(u,v)$,满足 $|dis_u-dis_v| \leq 1$
3. 设最长路径为 $k$,那么 $[0,k]$ 被 $dis$ 遍取。

我们发现从 $1,2$ 可以推出 $3$,所以我们只需要考虑满足 $1,2$ 限制。
我们首先发现一个点的 $dis$ 只有可能是 $[0,n-1]$,所以相当于是 $n$ 个不同的状态,并且代价也很好计算出来。
所以这个题的图就很好建出来了。。。沿用上一题的做法,边容量为这个点 $dis$ 为这个状态的时候对答案的贡献。
现在还有一个小问题:处理限制 $1$ 。
我们发现只需要让第一行强制选边 $0$ (边权为 $0$ 的状态容量为 $0$,其余容量为 $+\infty$),其余的点不允许选择边权为 $0$ 的状态(容量为 $+\infty$),然后直接跑网络流就可以了。

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/738
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 NOIP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

最小割模型
网络流题目中,如果一种物品有两种状态(选或不选),告诉你每一种状态产生的收益/代价,我们就可以通过使用最小割模型来解决这个问题。但是如果物品的状态扩展到了 $k$ 种,我们就需要用…
扫描二维码继续阅读
2019-08-01
标签
近期评论