Incubator

作者：赵晟宇

关键词：图论 最长反链 二分图匹配 传递闭包

题目简述

给定一张$n$个点的有向图。没有重边，可能有自环。每次操作可以激活任意一个点，代价是它能直接或间接到达的所有点都会被打上标记。问最多有多少个被激活的且没有被打上标记的点。

$1 \leq n \leq 50$

算法

等价于选出最多的一组点，使得其中不存在祖先关系。这样就转化为了经典的最长反链。

首先传递闭包（即对于每个点，向其间接可达的每个点都连一条有向边）。然后我们这样建立一张二分图：将原图拆点，对应着二分图中的$(1, 2, ..., n)$与$(1', 2', ..., n')$；若原图中u直接或间接连向v，则在二分图中建立$(u, v')$这样一条边。答案即为$n$减去最大匹配数。

我们再建立一张新图来证明这个结论。对于每条匹配边$(u, v')$，在新图中建立一条$(u, v)$的有向边。由于新图中每个点的入度与出度均最多为1，新图中只可能存在一些链与一些环（单点也算作一条链）。每条链上最多只能被选择一个点，而环上则无法选出任何一个点。所以对于任意一个匹配，答案严格小于等于新图中链的数量。求得最小链数即可。而新图中链的数量等于$n$减去匹配数，最大匹配数对应着最少的链。算法得证。

时间复杂度$O(n^3)$，空间复杂度$O(n^2)$。