Noi模拟 价 网络流 最大权闭合子图

https://ly.men.ci/problem/212

QwQ,,考场上看出来是最大权闭合子图了,然后依旧没有成功构建出图,GG。。。

先温习一下什么是最大权闭合子图,就是每个点有一个点权,而且如果你选了某个点,那么他所选的的后继的点都需要选。

具体的建图方式就是正权点向源点连边,边权为正权。负权点向汇点连边,边权为负权的绝对值,原图中的边统统都inf,然后正权和-最小割即为答案。

这道题给出了我们一个保证,保证N个药和N个药材可以完美匹配。而最后我们选也必定是选出K个药,选出了不小于K的药材。我们要做的就是保证药材和药相等的前提下,负权尽可能多。

这样子我们先把原先的负权换成正权,正权变负权,等最后求完结果再取反回来就好了。

我们认为每个药的点权是p[i]  + inf 每个药材的点券是-inf。然后建图,药连包含的药材。(注意此时p[i]已经取反了)

然后跑一下最小割,然后正权减一下,取个反就是答案了。为什么这么做是正确的。我们考虑一下,在刚刚的图中,如果我们选择的药材的数量多于药,那么最后的总收益是负无穷,显然最大权闭合子图,不会取到这种情况,我们肯定是每种药对应一种药材,不多不少。这样子显然是正确的。

这题若是谈到怎么想到这么做,大概是开始感觉这题肯定是最大权闭合子图,然而这种做法中,点权用边权表示,无法有效的限制流量。我们只能通过对权值的操作去避免非法的情况,所以想到了加正无穷的方法。还有要注意一下。原先你用的各种正无穷应该用一个更大的值来代替。

在考场上还是应该多去尝试思考和解决问题,很多时候不能抱着一个目前行不通的算法尝试改良。

 

发表评论