祭祀

· · 个人记录

本题即求最大的独立点集。

如果设关系为两点是否可达，然后做一遍传递闭包，我们就把原问题转化为了图的最大反链。

最大反链就是说，在这条链上的所有点，都不满足这一偏序关系。我们统计最大反链的数量就是第一问的答案。

这怎么做？根据 Dilworth 定理，最大反链等于最小链覆盖，后者是经典题。匈牙利或者 Dinic 都好，前者好写。

然后看第二问，也就是构造一组解。

最开始感觉这问挺水的，好像很好构造，但是实际上比第三问麻烦。

我们先第一问匹配出来，然后从右边的非匹配点开始 DFS，右点只走非匹配边，左点只走匹配边，我们就可以知道哪些点被 DFS 到。

取集合 S 代表左边被访问到与右边没有访问到的点的并，那么 S 是一个最小点覆盖，它的补集就是最大独立集。

为啥？

点覆盖指的就是使得每条边的两个端点至少有一个被覆盖的点的集合。根据我们上面的构造方法，右边选取的点一定是匹配点。而如果一个右边的匹配点没有被选入，其一定是由左边某个匹配点访问到了，否则就产生了一条增广路，就不是最大匹配了。因此，一条边要么被左边点选中，要么被右边点选中。

根据这样，我们取 S 的补集就能得到构造方案。

第三问要求我们判断一个点是否可能在最大独立集中。强制选择这个点，删除与它有关的所有点，然后再跑一遍就可以了。