主题

主题

 
   

#77. A+B Problem

原题:http://uoj.ac/problem/77/http://www.lydsy.com/JudgeOnline/problem.php?id=3218

(UOJ的markdown写法就不贴题面了)

题目大意:

给出n个元素,每个元素是一个六元组(a,b,w,l,r,p)。

现在要求把格子染成黑色或者白色,并计算权值:

  1. 如果当前格子i为黑色得到bi的权值,反则得到wi的权值

  2. 如果当前格子i为黑色,且在当前格子i之前,存在一个或者多个格子j,有li<=aj<=ri,那么需要扣除pi的权值

最大化权值。


个人解法:

朴素的最小割还是比较容易的。

首先从s到i连一条<vol=bi>的边,i到t连一条<vol=ai>的边。新建n个虚点,i的虚点即为i+n,i+n向所有li<=aj<=ri的j(其中1<=j<i)连一条<vol=none(正无穷)>的边。

这张图的最小割就是最小的代价。用sigma(ai+bi)减去最小割即可。

但是边数极高。

我们考虑拿到一棵以ai为下标的前缀线段树。我们用这棵前缀线段树来连边即可。

那么拿到前缀线段树,我们可以通过主席树来实现。


细节问题:

如果存在ai相同的话,一棵主席树会新建节点,那么可能到不了之前的节点了。

所以,如果在建立当前节点的主席树的时候,如果发现之前有一个点ai相同,那么把这两个线段树节点相连。

比方说这样:

黑色的边是主席树新建的边,红色的边是赋值原有的边。


橙色的边即为在a[3]=a[4]的情况下连接的。可以考虑一下如果不连接这条边,从4走入4的前缀线段树是走不到3的。


代码如下:

http://uoj.ac/submission/134664

 
 
评论