[BZOJ 1497][NOI 2006]最大获利(最大权闭合子图)

题目:http://www.lydsy.com:808/JudgeOnline/problem.php?id=1497

分析:

这是在有向图中的问题,且边依赖于点,有向图中存在点、边之间的依赖关系可以考虑最大权闭合子图

假设a与b之间有权值为c的边(根据题意是双向边)

那么我们可以建一个新节点,点的权值为c,并指向a点和b点(单向),同时断掉原本a,b之间的双向边,a,b的点的权值是它们的花费(负的)

那么对于原问题就转化成了求最大权闭合子图的问题了

————————————————————————————————————————————————————————————————

                           最大权闭合子图

定义:有向图中选出一个点集V',必须满足对于V‘中的每个点,它的后继也在V’中,选出所有点权值和最大的点集V‘

算法:

弄一个源点S,汇点T,S连向所有权值为正的点,容量为点的权值,所有权值为负的点连向T,容量为点的权值的绝对值。

最后ans=图G中所有权值为正的节点的和-最小割

证明:http://wenku.baidu.com/link?url=Q7LKOvCRFeMQkY1WulrZTAHjN3ud8gbhuqUOKwPbwmGDAmCB0_URdEkJ59WKWVRGn9xSg9TgbWSmhhBIMxvGS2wMbENrxre6ZuSeO2v3mX7

然后这里我也来说一说:

1、首先因为原图中的边全是+inf,所以割边一定是S连出的边或者连向T的边

2、假设最小割割完后,S所在集合为A,T所在集合为B,那么A和B一定是闭合子图(S,T点除外)

因为如果假设A不是闭合子图,那么就说明A中的某一个节点的后继在B中,也就说明最小割把这条边给割掉了,但是原图中的边全是inf,所以不可能被割掉,所以假设不成立,所以A一定是闭合子图,B也一定是闭合子图(同理)

3、接下来我们只要说明对于最小割情况下的A集合,一定是最大的闭合权子图

对于随便任意一个割C(当然还是不会割掉容量inf的边)

则C为B中所有权值为正的点权和(即S连出的边被割掉的总量)+B中所有权值为负的点权绝对值和(即连向T的边被割掉的总量)(C=x1+y1)

设A集合对应的闭合图的权值和W,则W=A中权值为正的节点的权值和-A中权值为负的节点的权值绝对值和(W=x2-y2)

相加得W+C=x1+x2+y1-y2

y1和y2显然相等

所以W+C=x1+x2=原图中所有权值为正的点权和(这是个常数!)

所以C越小,W就越大,于是就相当于求最小割了

——————————————————————————————————————————————————————————————————

其实这一题有更优的算法,详见2007年集训队论文

上一篇:MySQL命令行登录的例子


下一篇:HTTP和GET/POST请求(NSURLConnection)