题目链接： AcWing 379. 捉迷藏
题目大意：
给定一张 \(N\) 个点，\(M\) 条边的有向无环图，求最多能选取的点数 \(K\)，使得选取的任意两点都没有路径相连。
\(N\leq 200, M\leq 30000\)
思路：
可以发现选取的点是路径的起点时最保险的，这时该点不能从任何地方到达，这样我们注意到一条路径上其实最多只能选取一个点，则 \(|select|\leq |path|\)，在所有的路径方案中，有一个最低的上限，即最小路径可重复点覆盖的大小，下面用 \(path\) 表示该情况的边集。
接下来尝试构造 \(|select|=|path|\) 的取点，若方案存在，则答案 \(K\) 即为 \(|path|\) 。
对原图 \(G\) 进行传递闭包，得到新的 \(DAG\) \(G‘\)，首先构造 \(path\) 的具体方案：
路径覆盖包含的路径条数最少
\(\iff\) 路径终点数（出度为 \(0\) 的点数）最少
\(\iff\) \((x,y) \Rightarrow (x,y+n)\) 构造的拆点二分图 \(G_2‘\) 左部非匹配点最少 （二分图具体可以参考这一篇）
在最优情况下，每一条路径的起点入度和终点出度必然为零，设节点 \(x\in G‘\) 在 \(G_2‘\) 中对应左部点 \(x\) 和 \(x‘\) ：
- 依次考虑左部每一个非匹配点 \(x_0\) 。
- 从 \(x_0\) 出发，不断访问 \(x_0\) ，\(match[x_0‘]\) ，\(match[match[x_0‘]]...\) 直至到达一个左部点 \(y_0\) \(s.t.\) \(y_0‘\) 是非匹配点。
- 在 \(G‘\) 中，节点 \(x_0\)，\(y_0\) 以及刚才经过的点构成一条路径。
这样找到的所有路径就是 \(path\) 的方案之一，所有路径在 \(G‘\) 上是不相交的。
接下来构造 \(select\) ：
- 选出 \(path\) 中每条路径的终点 \(x_0\) ，构成一个集合 \(E\) 。
- 求出从 \(E\) 中节点出发，走一条边，到达的集合 \(next(E)\) 。
- 根据传递闭包的性质， \(G\) 中任意两个选取的点没有路径相连，等价于 \(G‘\) 中任意两个藏身点都没有边相连。因此，若 \(E\bigcap next(E)=0\) ，则 \(select=E\) 即为所求。
- 否则，考虑 \(E\bigcap next(E)\) 中的每一个节点 \(e\) ，沿着 \(e\) 所在的路径向上走，直到一个节点 \(e‘\notin next(E)\) 。从 \(E\) 中删除 \(e\) ，加入 \(e‘\) 。
- 对于修改后的集合 \(E\) ，重复执行步骤 \(3\) 和 \(4\) ，直到步骤 \(3\) 中的条件满足。
可以证明，任何时刻在步骤 \(4\) 中，我们一定能找到合法的 \(e‘\) 。这是因为如果找不到这样的 \(e‘\)，就说明 \(e\) 所在的路径（记为 \(pe\)）上的所有点都能够被其他路径的终点到达。设 \(pe\) 的起点是 \(y_0\)，我们可以延长那条到达 \(y_0\) 的路径，代替 \(pe\) 去覆盖 \(pe\) 上的所有节点，使集合 \(path\) 中的路径减少一条，与 \(path\) 的最小性矛盾。
你认为这道题做完了？并没有。手头有《算法竞赛进阶指南》的读者可以发现这段构造和反证跟书上的文字一模一样，如果你仔细去思考一下这个反证，与我尝试解释去解释它的时候一样，会发现这是有逻辑漏洞的。
这个反证法的说明其实只适用于第一个要找的 \(e‘\)，对于后面的调整， \(next(E)\) 中不仅仅有终点的相连点了，还有已经调整好的点的相连点。也就是说，此时这个路径不一定能被完全替代，别的路径走过来可能需要在中间拐个岔子，而不是到了终点再往这条路径上走。
不过这个构造是无懈可击的，题目后面其实有一个更加深刻的东西支撑其正确性：
\(Dilworth\) 定理：对偏序集<A，≤>，设A中最长链的长度是n，则将A中元素分成不相交的反链，反链个数至少是n。
这个定理可以说明对于任意有限偏序集，其最大反链中元素的数目必等于最小链划分中链的数目，而最大反链大小即为此题所求的 \(K\) 。其证明可以在网上查到，其中与图论紧密相连的有这一篇。
身为中学生，个人知识水平有限，不能进一步延伸，比较感兴趣的就自己上网了解一下吧。。
?
实现
对原图进行传递闭包，然后求出拆点二分图的最大匹配，答案即为 \(N\) 减去最大匹配数，时间复杂度 \(O(N^3)\) 。
由于二分图实际上只遍历其中一边，所以二分图不拆点跑匈牙利是不影响正确性的。
Code:
#include<iostream>
#include<cstring>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,b,a) for(int i=b;i>=a;i--)
#define N 220
using namespace std;
bool conn[N][N],vis[N];
int match[N],n;
bool dfs(int x){
rep(y,1,n)if(conn[x][y]){
if(vis[y])continue;
vis[y]=true;
if(!match[y]||dfs(match[y])){
match[y]=x; return true;
}
}
return false;
}
int main(){
int m,a,b;
cin>>n>>m;
rep(i,1,m){
cin>>a>>b; conn[a][b]=true;
}
rep(k,1,n)rep(i,1,n)rep(j,1,n)
conn[i][j]|=conn[i][k]&conn[k][j];
int ans=n;
rep(i,1,n){
memset(vis,false,sizeof(vis));
ans-=dfs(i);
}
cout<<ans;
return 0;
}