【BZOJ1006】神奇的国度 - 弦图MCS算法

看了好久cdq的PPT才搞懂,其实也挺简单的,虽然这类型的题目不会很多(主要是不一定满足弦图的性质),但是用了还是效果不一般的。

题目大意

  K国是一个热衷三角形的国度,连人的交往也只喜欢三角原则.他们认为三角关系:即AB相互认识,BC相互认识,CA相互认识,是简洁高效的.为了巩固三角关系,K国禁止四边关系,五边关系等等的存在.所谓N边关系,是指N个人 A1A2...An之间仅存在N对认识关系:(A1A2)(A2A3)...(AnA1),而没有其它认识关系.比如四边关系指ABCD四个人 AB,BC,CD,DA相互认识,而AC,BD不认识.全民比赛时,为了防止做弊,规定任意一对相互认识的人不得在一队,国王相知道,最少可以分多少支队。

参考资料:弦图与区间图-cdq

简单介绍一下算法。

从题目描述中以及弦图的定义我们可以发现,K国的认识关系是弦图。于是现在我们要做的就是求出弦图数最小点染色数。

从cdq的PPT中我们可以得到这样的结论: 完美消除序列从后往前依次给每个点染色,给每个点染上可以染的最小的颜色 ,可以得到最小染色数。

证明见PPT。

于是我们的目标就是求完美消除序列。

在PPT中cdq介绍了LexBFS和MCS算法,前者太复杂,我介绍一下后者。

n1的顺序依次给点标号(标号为i的点出现在完美消除序列的第i)label[i]表示第i个点与多少个已标号的点相邻,每次选择label[i]最大的未标号的点进行标号。

这一步实现可以用优先队列来完成,然而复杂度是O(MlogM)。这样在M太大的时候容易go die,所以我们可以使用链表的方法来记录最大的label。

以下转自noip吧jcvb

由于每个点的label不会超过n-1,因此我们可以维护每个结点的label,并维护n个链表,分别表示label为0~n-1的结点各有哪些。

然后维护一个best值表示当前最大的label,再开一个vis数组记录每个点是否已被取出放入序列。

初始时每个点label为0,都放在0号链表里。best=0。

①更新操作:某结点u的label从x变为x+1时,只要把u插到x+1链表的头部,无需将其从x链表中删除(所以不用写双向链表)。然后更新best值。

②取最大操作:取最大label结点时从best链表的头开始取,如果取到的是已被放入序列的结点就删除并继续往后取,仍取不到则--best,直到取到一个未被放入序列的点。

操作①每次O(1),总共执行O(m)次。best++也被执行O(m)次,那么操作②中--best也只有O(m)次。操作①每次插一个结点,则总共有O(n+m)个结点,而操作②中每往后取一个就删一个,所以也是O(n+m)。

这里大概就是最难懂的部分了,其它的参考cdq的PPT~

 

不如来评论一发?