joyoi1957 「Poetize5」Vani和Cl2捉迷藏

最小路径可重点覆盖。先传递闭包，然后拆点，(n-)最大匹配，看算法竞赛进阶指南。

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int n, m, uu, vv, mat[205], ans;
bool w[205][205], vis[205];
bool hung(int x){
	for(int i=1; i<=n; i++)
		if(w[x][i]){
			if(vis[i])	continue;
			vis[i] = true;
			if(!mat[i] || hung(mat[i])){
				mat[i] = x;
				return true;
			}
		}
	return false;
}
int main(){
	cin>>n>>m;
	for(int i=1; i<=m; i++){
		scanf("%d %d", &uu, &vv);
		w[uu][vv] = true;
	}
	for(int k=1; k<=n; k++)
		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				w[i][j] |= w[i][k] & w[k][j];
	for(int i=1; i<=n; i++){
		memset(vis, 0, sizeof(vis));
		if(hung(i))	ans++;
	}
	cout<<n-ans<<endl;
	return 0;
}