P10938 Vani和Cl2捉迷藏 题解
Planetary_system
·
·
题解
题面解释：
## 思路分析：
根据题意连起来的点只能取一个，即求最大点独立集。果断建二分图，求最大匹配。使用匈牙利算法即可。
关于匈牙利算法，即求二分图最大匹配的一种优质算法，好学好用，具体见 [这里](https://www.luogu.com.cn/article/nez5vwet)。简单地说，就是每次枚举边，能连则连，不能连则尝试让原先连好的边换一条连，递归下去，若当前点成功连接则说明增加了一条匹配，最终答案就是总数减去匹配数。
这样，你可以获得 `95pts` 的高分而 `WA`。（本不应有这么多分，数据有点水。）这时候反观题目，发现边具有传递性，即若 $1$ 指向 $2$ 而 $2$ 指向 $3$，$1$ 与 $3$ 同样不能共存，所以我们先跑一遍 $\text{Floyd}$ 即可。
## Code
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=210;
int n,m,t,vis[N],mch[N],g[N][N];
bool dfs(const int u, const int tag) {
if(vis[u]==tag)return 0;
vis[u]=tag;
for(int i=1; i<=n; i++)
if(g[u][i]&&((mch[i]==0)||dfs(mch[i],tag)))
{mch[i]=u;return 1;}
return 0;
}
signed main() {
scanf("%d%d",&n,&t);
for(register int i=1,x,y; i<=t; i++)
scanf("%d%d",&x,&y),g[x][y]=1;
for(register int k=1; k<=n; k++)
for(register int i=1; i<=n; i++)
for(register int j=1; j<=n; j++)
g[i][j]|=g[i][k]&g[k][j];
int res=n;
for(register int i=1; i<=n; i++)
res-=dfs(i,i);
printf("%d",res);
return 0;
}
```
谢谢！