题目链接：
题目描述：
在外星上有n个点需要机器人去探险，有m条单向路径。问至少需要几个机器人才能遍历完所有的点，一个点可以被多个机器人经过。
解题思路：
一眼看上去是普通的最小边覆盖，但是仔细想后发现如果在原图上进行最大匹配的话，每个点只能经过一次。这样的话对于本题求出的并不是最优解，所以我们要先对原图进行传递闭包处理，然后再进行最大匹配。
这个题目点数太少H_K和匈牙利算法在空间和时间上并没有什么差，就代码复杂度而言匈牙利算法更有优势。
#include <iostream>//匈牙利算法
#include <cstring>
#include <queue>
#include <cmath>
#include <cstdio>
using namespace std; const int maxn = ;
int maps[maxn][maxn], n, m;
int used[maxn], vis[maxn];
void floyd ()
{
for (int k=; k<=n; k++)
for (int i=; i<=n; i++)
for (int j=; j<=n; j++)
if (maps[i][k] && maps[k][j])
maps[i][j] = ;
}
int Find (int u)
{
for (int i=; i<=n; i++)
{
if (!vis[i] && maps[u][i])
{
vis[i] = ;
if (!used[i] || Find(used[i]))
{
used[i] = u;
return ;
}
}
}
return ;
}
int main ()
{
while (scanf ("%d %d", &n, &m), n||m)
{
memset (maps, , sizeof(maps));
while (m --)
{
int u, v;
scanf ("%d %d", &u, &v);
maps[u][v] = ;
}
floyd ();
memset (used, , sizeof(used));
int res = ;
for (int i=; i<=n; i++)
{
memset (vis, , sizeof(vis));
res += Find(i);
}
printf ("%d\n", n - res);
}
return ;
}
#include <iostream>//H_K算法
#include <cstring>
#include <queue>
#include <cmath>
#include <cstdio>
using namespace std; const int maxn = ;
const int INF = 0x3f3f3f3f;
int maps[maxn][maxn], n, m, dx[maxn], dy[maxn];
int vis[maxn], cx[maxn], cy[maxn], dis;
void floyd ()
{
for (int k=; k<=n; k++)
for (int i=; i<=n; i++)
for (int j=; j<=n; j++)
if (maps[i][k] && maps[k][j])
maps[i][j] = ;
}
bool bfs ()
{
queue <int> Q;
dis = INF;
memset (dx, -, sizeof(dx));
memset (dy, -, sizeof(dy));
for (int i=; i<=n; i++)
if (cx[i] == -)
{
Q.push(i);
dx[i] = ;
}
while (!Q.empty())
{
int u = Q.front();
Q.pop();
if (dx[u] > dis)
break;
for (int i=; i<=n; i++)
{
if (dy[i]==- && maps[u][i])
{
dy[i] = dx[u] + ;
if (cy[i] == -)
dis = dy[i];
else
{
dx[cy[i]] = dy[i] +;
Q.push (cy[i]);
}
}
}
}
return dis != INF;
}
int dfs (int u)
{
for (int v=; v<=n; v++)
{
if (!vis[v] && dx[u]+==dy[v] && maps[u][v])
{
vis[v] = ;
if (cy[v]!=- && dis==dy[v])
continue;
if (cy[v]==- || dfs(cy[v]))
{
cx[u] = v;
cy[v] = u;
return ;
}
}
}
return ;
}
int Max_match ()
{
int res = ;
memset (cx, -, sizeof(cx));
memset (cy, -, sizeof(cy));
while (bfs())
{
memset (vis, , sizeof(vis));
for (int i=; i<=n; i++)
if (cx[i] == -)
res += dfs (i);
}
return res;
}
int main ()
{
while (scanf ("%d %d", &n, &m), n||m)
{
memset (maps, , sizeof(maps));
while (m --)
{
int u, v;
scanf ("%d %d", &u, &v);
maps[u][v] = ;
}
floyd ();
printf ("%d\n", n - Max_match());
}
return ;
}