您已获得最佳的阅读体验!
题目地址:P10938
题目难度:省选/NOI-
Vani 和 cl2 在一片树林里捉迷藏。
这片树林里有
座房子, 条有向道路,组成了一张有向无环图。 树林里的树非常茂密,足以遮挡视线,但是沿着道路望去,却是视野开阔。
如果从房子
沿着路走下去能够到达 ,那么在 和 里的人是能够相互望见的。 现在 cl2 要在这
座房子里选择 座作为藏身点,同时 Vani 也专挑 cl2 作为藏身点的房子进去寻找,为了避免被 Vani 看见,cl2 要求这 个藏身点的任意两个之间都没有路径相连。 为了让 Vani 更难找到自己,cl2 想知道最多能选出多少个藏身点。
对于
的数据, , , 。
乍一看好像求最大点独立集的问题,但是它只存在于无向图中,题目所给是有向图。这道题的答案是该图的最小重复路径点覆盖的路径条数。那么什么是路径点覆盖呢?
在图上选取若干条互不相交的路径,并让这些路径不重不漏覆盖到每一个点。符合上述要求且总数最小的方案就叫做原图的最小路径点覆盖,图中每个节点均只被覆盖一次。而最小重复路径点覆盖则是允许选取的路径相交,即某个点至少被覆盖一次。
在二分图中,最小路径点覆盖的路径条数等于总点数减去最大匹配数;最小路径重复点覆盖的数量则需要先求传递闭包,再计算最小路径点覆盖得出。
这启发我们可以把图转化为二分图来做,具体流程如下:
- 原图中的点
,在二分图中变为 和 - 对于原图所有形如
的边,在二分图上连 ;对于所有形如 的边,在二分图上连边
就可以把原图当二分图求解了。
接下来证明为什么答案就是原图的最小重复路径点覆盖。设答案为
- 证明
,考虑最小路径点覆盖的定义:因为 条路径已经把所有点覆盖了,选点只能选其中某条路径的某个端点,已知有道路相连的房屋是可以互相看到的,所以不可能同时选某条路径的两个端点(最多选一个)。因此选出的 是一定小于等于 的。 - 证明
,考虑构造:将所有路径的终点 放入一个集合 中, 为“从 出发能够到达的所有点的集合”。如果 ,均有 ,意味着 内任意两点不互通,此时 为一组合法方案,大小为 ;反之,让当前的 沿有向边反着走直到满足上面的情况。若当前点已经退回到它的起点,都还不满足上述情况,意味着这个起点与 中的所有点都互通,我们完全可以让 作为起点,所有点也都能被覆盖到,此时的最小路径点覆盖数为 ,与原图最小路径点覆盖数为 矛盾。故一定存在 。 - 综上,
必定成立。证毕。
此时使用匈牙利算法跑二分图最大匹配,然后就可以得出答案了。时间复杂度
1 |
|
瓦尼瓦尼和氯气?