POI2008 Mafia
题目大意:
有n个人,每一个人有一把手枪。一开始,所有的人都选定一个人瞄准(有可能瞄准自己)。然后他们按照某一个顺序开枪,且任意时刻只有一个人开枪。因此,对于不同的开枪顺序,最后死掉的人也不同。问最后死亡人数的最小和最大可能值。
( $nle 10^6$ )
题解:
首先很容易看出,图是一个基环外向树,那么我们就可以借助一些基环外向树的性质来解题了。
对于最大的可能人数,我们比较好得到。只要让存活人数最少就可以了,那么就让那些一定不会死的人活下来,其他人都可以杀掉。
不会死的人有两种:
- 入度为0的人。由于没有人拿枪瞄准他们,显然不会死。
- 当一个基环外向树没有”树枝”,而只有中间那一个环时,我们没有办法将环上的人全部杀完,总要留下一个。留下的那个就可以不用死。(中间的环不能是自环,不然当然可以把环上的人杀完)
利用拓扑排序随便搞一下,这部分就可以解决了。
接下来看看最小的可能人数:
一个人会不会死关键看是否有一个没死的人拿枪指着他。
也就是说,如果有一个人没死,那么被他指的人一定会死。
首先,入度为零的人,一定不会死,但是被他指的人全都会死。
为了让活着的人尽量多,我们不妨让死了的人都不开枪。
那么对于一个必死的人,他所瞄准的人都少了一次被杀死的机会,可以把它们的入度减一。
如果入度减为了零,说明所有的威胁都被排除,此人已经死不了了。
由此,我们可以把基环外向树上的”树枝”全部清理掉。
对于留下的环,我们从环上任意一个人开始,让他死,那么环也就可以流动起来了。
其实最小值也可以用树形dp来写。
题目转化一下就可以变为:
我们把基环外向树的边都变为双向的。然后在树上取一些点(表示这些点活着),且两个被取的点不能相邻,最大化取的点的数量。
Code:
原文:大专栏 POI2008 Mafia