RainAir
My OI Blog
RainAir
最大权闭合子图

题目链接

模型描述

有一个工厂,接到了 $n$ 个订单,为了完成这些订单,工厂需要采购一些机器,一共可采购 $m$ 台机器。我们知道完成每个订单的收益,也知道购买某个机器的开销。一个订单需要对应地购买某些机器,一台机器可以同时完成多个订单。现在工厂决定选择性地接一些订单,使得工厂的利润最大化。

解题报告

最大权闭合子图

我们来介绍一下什么是最大权闭合图。

闭合子图

定义一个有向图 $G(V,E)$ 的闭合子图为该有向图的一个子图 $G′(V′,E′)$ ,子图中每一个点的出边都指向这个子图里的点。例如下图就是一个闭合图。
https://blog.aor.sd.cn/wp-content/uploads/2018/12/pujsuawfw.png

最大权闭合子图

给每个顶点 $i$ 分配一个权值 $w_i$ ,最大权闭合子图就是点权总和 $\sum_{i∈V′} w_i$ 最大的闭合子图。
https://blog.aor.sd.cn/wp-content/uploads/2018/12/cspa.png
那么我们如何找到最大权闭合子图呢?
一般我们会将其转化为网络流模型。
具体来说:在原图的基础上新增加源点 $S$ 和汇点 $T$ ,原图所有边的流量设置为 $\text{INF}$ ,对于每一个边权为正的边,源点向其连一条流量为该点点权的边,对于每一个边权为负的边,这个点向汇点连一条流量为点权的绝对值的边。那么最大的权就是点权为正的点的点权和减去最小割,例如上图的例子可以转化为:
https://blog.aor.sd.cn/wp-content/uploads/2018/12/test.png
如何算方案呢?与源点相连的点都是最大权闭合子图的顶点。

证明

那么这个为什么是对的呢?我们尝试来证明它 $qwq$ 。

引理一:这个网络的最小割一定是一个简单割,也就是只会割直接与源点/汇点相连的边。

证明显然,没有与源点/汇点相连的边都是正无穷。

引理二:该图的每一个简单割产生的两个子图,我们记含有源点的图为 $S$ ,记含有汇点的图为 $T$ ,则图 $S$ 为闭合子图。

由于是简单割,所以 $S$ 中的任何一个节点都不能到达 $T$ ,所以该引理正确。

证明:最小割产生的图 $S$ 和 图 $T$ ,图 $S$ 为最大权闭合子图

因为割集中所有的边,不是连接到 $S$ 上,就是连接在 $T$ 上(引理一)。
我们记割边权值和为 $X$ ,割集中连接到源点的边的权值和为 $x_1$ ,连接到汇点的权值和为 $x_2$ ,则有 $X=x_1+x_2$ 。
记图 $S$ 的所有点的权值和为 $W$ ,记期中正权值之和为 $w_1$ ,负权值之和为 $−w2$ ,有 $W=w_1−w_2$ 。
所以有 $W+X=w_1−w_2+x_1+x_2$ 。
注意到 $x_2=w_2$ (图 $S$ 中点权为负的点一定一开始连接到汇点,后来被加入割集),可得 $W+X=w_1+x_1$ 。
显然 $w_1+x_1$ 是图中正点权权值和,记为 $SUM$ 。
因此 $W=SUM−X$ 。由引理二得知 $S$ 为一个闭合子图。$SUM$ 是一个定值,我们要使 $X$ 尽可能的小,也就是求最小割。

如何建模

我们把订单和机器都看成一些点,订单都为正边权,机器为负边权,订单指向这个订单需要的机器,显然这个图的最大权独立集就是答案(满足所有订单的最大收益方案)。

代码

(以链接里的题目代码为准,大同小异)

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/323
如文中无特殊声明,本文采用 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

最大权闭合子图
题目链接 模型描述 有一个工厂,接到了 $n$ 个订单,为了完成这些订单,工厂需要采购一些机器,一共可采购 $m$ 台机器。我们知道完成每个订单的收益,也知道购买某个机器的开销。一个…
扫描二维码继续阅读
2018-12-03
标签
近期评论