网络流练习笔记


一些常用的套路:

  • 必须完成的一些目标,可以考虑搞进流量中,因为跑最大流的话肯定会流满,也就相当于强制地完成了那些目标。
  • 拆点。然后可以通过两点之间连某个容量的边来限制该点取到的次数。
  • 建立超级源点、汇点。几乎在每道题中都会用到,不光方便计算,还可以通过连边的方式对某些状态进行操作。

P1251 餐巾计划问题

发现每天开始和结束时的状态是不一样的,考虑拆点。

接着怎么办?模拟餐巾的路线吗?

假如从白天向晚上连一条边表示餐巾由干净变为脏的话,会发现根本无法处理每天的需求量。

那反正只要是干净的就行了,咋来的咱不管,那就直接从超级源点流过来嘛。然后就可以让餐巾流到超级汇点来完成需求啦!

具体分以下几种:

  • 由超级源点向每天晚上连一条容量为当日需求,费用为 \(0\) 的边。表示晚上获得脏餐巾。
  • 由每天早上向超级汇点连一条容量为当日需求,费用为 \(0\) 的边。表示白天需要新餐巾。
  • 由每天晚上向次日晚上连一条容量为 \(\infty\),费用为 \(0\) 的边。表示餐巾不洗留到下一天。
  • 由每天晚上向现在送去快洗能洗好的那天早上连一条容量为 \(\infty\),费用为快洗费用的边。表示送去快洗。
  • 由每天晚上向现在送去慢洗能洗好的那天早上连一条容量为 \(\infty\),费用为慢洗费用的边。表示送去慢洗。
  • 由超级源点向每天早上连一条容量为 \(\infty\),费用为购买新餐巾费用的边。表示购买新餐巾。

然后跑最小费用最大流。

值得注意的是,第三点处于贪心的考虑,肯定会直接洗掉。但我们发现设计的方案中并没有设置这样一个库存餐巾,所以就得通过这一步来使得餐巾能够在必须洗的那天晚上刚好洗掉,从而达到和提前洗完一样的效果。所以如果某天晚上就算送去快洗也洗不完了,前一天晚上的这条边可以不连。

P4015 运输问题

乱翻网络流二十四题时有幸看到这个帖子

故在此说明一点:最长路径问题是 NP-HARD 的原因是可能存在正权圈,这种情况下要求最长简单路径。类似地,存在负权圈的最短简单路径也是 NP-HARD 的。详情可以看这个回答

每个仓库向每个零售商店连容量为 \(\infty\),给定费用的边。再从超级源点向每个仓库连容量为给定数量,费用为 \(0\) 的边;从每个零售商店向超级源点连容量为给定数量,费用为 \(0\) 的边,最后跑最大费用最大流。直接将权值取反然后再跑一遍最小费用最大流即可,记得跑完一遍后记得重置每条边当前流量。

其实这种简单题的建模不难,对着题意模拟,把每种可能的情况考虑进去就行了。

P4013 数字梯形问题

如果理解了最上面三条东西可以秒杀。

路径互不相交说明啥?点不能重复选呗,那就拆点然后两点之间连容量为 \(1\) 的边。

路径仅允许在数字结点处相交说明啥?边不能重复选,点可以重复选呗,那就两点之间容量搞成 \(\infty\),从上一层走到下一层的边容量搞成 \(1\)(容易发现上一种情况这里设成大于 \(1\) 的都可行)。

路径随便相交怎么办?除了从超级源点到最上面的 \(m\) 个点容量设为 \(1\) 外其它容量全部 \(\infty\) 呗。

P2765 魔术球问题

神仙题,真的神仙。

依次塞球,如果塞不下了就加一根柱子,直到柱子不够为止。

那么具体咋建图呢?依旧考虑拆点,但拆点的作用有所不同,这里仅仅是为了方便处理,将每个球拆成出球(叠在一个球上面)和入球(一个球叠在它上面)。

从超级源点向每个入球连容量为 \(1\) 的边,从每个出球向超级汇点连容量为 \(1\) 的边。再从每对合法的较小的入球向较大的出球连边。

可以发现,从超级源点到超级汇点最长只存在长度为 \(3\) 的正向路径!举个栗子:\(S\to in_1\to out_3\to T\)

但这样恰好代表了一个球的堆叠!接下来:\(S\to in_3\to out_6\)

这样就堆叠了两个球!所以就这样每次新加一个球,如果最大流没有增加,说明需要一根新的柱子。

接着来考虑第二问:怎么找方案?

好像把所有路径撸出来然后重组一下是可行的,但这里给一种普适性很差的做法(显然本题流量仅有 \(0\)\(1\))。

考虑一条正向边,如果它被选了,那么流量一定为 \(1\)。DFS 下去,遇到这样的边并且出点还没有用过,就把流量置为 \(1\) 然后继续递归下去。

从超级汇点到入球都没有问题,到出球时直接输出。

至于正确性嘛,流量为 \(1\) 的边肯定是流满的嘛,那还能咋流呢?不可能出现两条同时流满的边嘛。

P2774 方格取数问题

黑白染色,由相邻的黑点向白点连容量为 \(\infty\) 的边。

黑点接到超级源点上,白点接到超级汇点上,权值为对应的数。

想要合法,无非就是一些点不选。显然中间的边是不会去删的,只会删两边的边。求出最小割(不连通说明合法)然后拿总权值减一下就好了。

本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。

  • 分享:
评论
还没有评论
    发表评论 说点什么