RainAir
My OI Blog
RainAir
网络流建模总结
网络流建模总结

输出方案

回忆前面我们解决二分图的方法:源点向每个左端节点连一个容量为 $1$ 的弧,每个右侧端点向汇点连一个容量为 $1$ 的弧,原图中的边容量为 $1$;所以说如果我们想获取方案的话我们只需要遍历左端点相连的弧是否满流即可。

交叉分组

https://blog.aor.sd.cn/wp-content/uploads/2018/12/QQ20181215-175032.png
建图方法显然,每个班级和每个小组都看成一个点。源点连向每个班级一条容量为 $a_i$ 的弧,每个小组连向汇点一条容量为 $b_i$ 的弧。之后对于每一个班级都连向所有的小组一条容量为 $1$ 的弧,最后判断最大流是不是等于总人数,如果是的话就输出即可。

二分答案

在网络流题目中有一类题目可以归纳为“满足条件的最极值”的问题,需要用到二分答案然后建立网络流判断的问题,大体来说不难但是记住每次都要清空网络流防止爆炸。

拆点

一般拆点有两种情况:对点做限制或者根据题目描述有意义的进行拆分。我们重点来讲述一下第一类题目。
当我们对点有容量限制时,就需要把点拆成两个。对于下面这个网络:
https://blog.aor.sd.cn/wp-content/uploads/2018/12/6f1010d5670ea9b28de419a12ed0d033b735cc07.png
如果我们想限制所有点的流量不超过 $3$,我们可以对于每一个点 $u$ 都拆成 $u’,u”$,将每条连入 $u$ 的点连入 $u’$,每条从 $u$ 连出的点改为由 $u”$ 连出,从 $u’$ 向 $u”$ 连一条容量为 $3$ 的弧。https://blog.aor.sd.cn/wp-content/uploads/2018/12/921288a95842084a40dcf9ab61daa5540b7a8905.png
如果点有费用的话,只需要在拆点后的边加上费用就好了。

「BZOJ1738」

这是一道权限题题面可以从这里看:链接
题目大意:一张无向图,边有边权,现在每个点上有一定的奶牛,每个点有一个可以容纳奶牛的最大数字,这样其他的奶牛就要移动到其他的点上,求让所有奶牛都有地方容纳的最小距离。
我们先考虑判断是否能让所有奶牛都能被容纳:显然对于每个点可以容纳这个限制我们可以拆点,源点连向每个点的第一个点一条流量为牛的数量的弧,每个点的第二个点连向汇点一条流量为可以承受的牛的容量的弧,原图的边流量设为 $INF$ 即可。
显然现在我们可以枚举这个答案 $L$ ,首先 $O(n^3)$ 跑一边 Floyd 预处理点对距离,然后枚举点对距离 $\leq L$ 的建流量为 $INF$ 的弧。判断是否可行即可。

增加限制点

有时候我们希望对一组点或者总容量进行限制,这时候就要通过增加限制点来实现。
比如我们想在二分图匹配上增加一些限制:对于左侧集合的某些顶点,如 ${1,2,4}$,其中最多只能有 $2$ 的节点能在最终的匹配中。先来回顾一下二分图匹配相应的网络:
https://blog.aor.sd.cn/wp-content/uploads/2018/12/501574af5cd75cc2eba5e281e6ce5a51e05e2fe6.png
我们可以在源点和左侧顶点之间增加一个限制点:源点流入该点的弧容量为 $2$ ,该点连向 ${1,2,4}$ 这三个顶点。
https://blog.aor.sd.cn/wp-content/uploads/2018/12/20d5fa9496e5d493fefd855b4593daaff135fb2f.png
这样就能确保 ${1,2,4}$ 至多有两个出现在最终的匹配方案中。

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

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

网络流建模总结
输出方案 回忆前面我们解决二分图的方法:源点向每个左端节点连一个容量为 $1$ 的弧,每个右侧端点向汇点连一个容量为 $1$ 的弧,原图中的边容量为 $1$;所以说如果我们想获取方案的话我…
扫描二维码继续阅读
2018-12-15
标签
近期评论