[题目链接]
https://www.lydsy.com/JudgeOnline/problem.php?id=1143
[算法]
答案为最小路径可重复点覆盖所包含的路径数，将原图G进行弗洛伊德传递闭包，得到一张新图G'，然后求出拆点二分图G2'的最大匹配，N - 最大匹配 即为答案，我们尝试证明上述结论 ：
设祭祀点集合为S，最小路径可重复点覆盖的边集为Path,由于Path覆盖了所有节点，故每条路径上至多选一个点，有 ： |S| <= |Path| , 因此，如果我们能构造出一组解，使得| S | = | Path | ， 就证明了此结论，这里给出一种构造方案 ：
首先求出拆点二分图的最大匹配，设节点x在拆点二分图上分别对应左部节点x和右部节点x' , 对于每个非匹配节点x0,我们不断访问 x0,match[x0'],match[ match[x0'] ] .. 直到最后遇到一个左部节点y0,使得其右部点y0'为非匹配点， 那么就得到了一条路径， 其中y0为起点，x0为
终点，求出这样的所有路径，就得到了| Path |的一种方案，且所有路径不相交，我们现在要将| Path |集合中的每条路径选出一个节点，构成集合| S |
首先我们将所有路径的终点构成一个集合E,根据传递闭包的性质，两个祭祀点之间无路径相连，等价于在新图G’上任意两个祭祀点之间没有边，不妨让集合E中的每个节点走一条边，构成集合Next(E),如果E和Next(E)的交集为空集，则S = E
否则，对于交集中的每个点e,我们沿着e所在的路径不断向上移动，直到e不在当前的交集中，从E中删除e，加入e',重复以上过程，直到交集为空，就求出了S的一种组成方案
可以证明，在任何时刻，我们都能找到合法的e'，因为若没有，说明e所在的路径上所有点都可以被其他路径上的点到达，我们可以找到到达e所在的的路径起点的那条路径，将其延伸，使得| Path | 减少1，并覆盖所有节点，与Path的最小性矛盾
综上所述，答案即为最小路径可重复点覆盖所包含的路径数
[代码]
#include<bits/stdc++.h>
using namespace std;
#define MAXN 210 int i,j,k,n,m,u,v,ans;
bool g[MAXN][MAXN],mp[MAXN][MAXN];
bool visited[MAXN];
int match[MAXN]; inline bool hungary(int u)
{
int v;
for (v = ; v <= n; v++)
{
if (mp[u][v] && !visited[v])
{
visited[v] = true;
if (!match[v] || hungary(match[v]))
{
match[v] = u;
return true;
}
}
}
return false;
} int main()
{ scanf("%d%d",&n,&m);
for (i = ; i <= n; i++) g[i][i] = true;
for (i = ; i <= m; i++)
{
scanf("%d%d",&u,&v);
g[u][v] = true;
}
for (k = ; k <= n; k++)
{
for (i = ; i <= n; i++)
{
for (j = ; j <= n; j++)
{
g[i][j] |= g[i][k] & g[k][j];
}
}
}
for (i = ; i <= n; i++)
{
for (j = ; j <= n; j++)
{
if (i != j && g[i][j])
mp[i][j] = true;
}
}
ans = n;
for (i = ; i <= n; i++)
{
memset(visited,false,sizeof(visited));
if (hungary(i)) ans--;
}
printf("%d\n",ans); return ; }