Description:


Input:


Output:


最多可选多少景点

Sample Input:


Sample Output:


题解:


这一题算是最长反链的模板题~

如果不知道最长反链的定义的话题目里就有,也就是最大的点集不能一个点到达另一个点。

因为最长反链等于最小路径覆盖(因为每一条路径上取最后一个点就可以满足条件),而最小路径覆盖等于原图传递闭包后的最小链覆盖,最小链覆盖又等于改造成二分图后n-最大匹配。(有点绕(⊙o⊙)…)

所以对原图传递闭包后在上匈牙利暴力一下就可以了~

代码如下: