原题链接
这里有一个结论：最多能选取的藏身点个数等于最小路径可重复点覆盖的路径总数。
所以我们可以先传递闭包，然后求最小路径点覆盖即可。
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 210;
int mtc[N], n;
bool a[N][N], v[N];
inline int re()
{
int x = 0;
char c = getchar();
bool p = 0;
for (; c < '0' || c > '9'; c = getchar())
p |= c == '-';
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
return p ? -x : x;
}
bool dfs(int x)
{
int i;
for (i = 1; i <= n; i++)
if (a[x][i] && !v[i])
{
v[i] = 1;
if (!mtc[i] || dfs(mtc[i]))
{
mtc[i] = x;
return true;
}
}
return false;
}
int main()
{
int i, j, m, k, x, y, s = 0;
n = re();
m = re();
for (i = 1; i <= m; i++)
{
x = re();
y = re();
a[x][y] = 1;
}
for (k = 1; k <= n; k++)
for (i = 1; i <= n; i++)
if (i ^ k)
for (j = 1; j <= n; j++)
if (i ^ j && j ^ k)
a[i][j] |= a[i][k] && a[k][j];
for (i = 1; i <= n; i++)
{
memset(v, 0, sizeof(v));
s += dfs(i);
}
printf("%d", n - s);
return 0;
}