BZOJ 2768 [JLOI2010] 冠军调查


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2768

题意:同 BZOJ 1934 [Shoi2007]Vote 善意的投票


时隔一个月后才做到的双倍经验题... 感觉还是挺有趣的

别说会做了... 之前的自己连这么裸的建图都不理解... 蒟蒻认为网络流建模需要一个系统的思路,下面简单说一下自己的思路

首先看到原题,题意可以抽象成:对于每个点有两个 决策 ,每个决策会带来一定的 代价 ,求最小总代价。

通过流量限定决策,通过费用限定代价 是很显然的费用流模型,所以可以朴素的向费用流考虑,然而此题有一个特殊的性质——代价和决策都是非 0 即 1 的,所以费用和流量实际上没有区别,可以最小割解决,只需要考虑 决策 ,不需要考虑 代价

具体怎么搞呢?首先最小割跑完后的残量网络一定是我们希望的决策状态,如果没有朋友关系这个限定,显然直接给每个人分配自己所喜欢的即可了,这样的图一定是不连通的,根据自己喜欢的是 1 还是 0 分别连向 S 和 T,这就是在不考虑朋友关系下的状态。现在我们考虑朋友关系,一组朋友关系的实质其实是让两个人存在矛盾,把两个人连起来了,即可能导致存在 S-T 的通路。那么可以在两个人之间连一条无向边。这样建立的新图 S-T 是连通的,我们考虑通过 决策 来使得 S-T 回到不连通的理想状态——最小割。

那么回到问题,我们有什么可选的 决策 呢?如果我们目前的决策均能在建出的图中正确的抽象出来,那么这个建图就是正确的了,否则针对性的修改即可。首先我们可以让两个矛盾的朋友中的一个选择自己不喜欢的那个,即割掉一条 (S,i)/(T,i),显然原图不连通,或者可以接受这对矛盾关系,即不改变选项,割点朋友间的无向边,这样也是合法的 决策

当我们满足了整道题的所有 可能决策代价 后,建模就正确啦!

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 2768 [JLOI2010] 冠军调查


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , ,