题目链接：POJ2594-Treasure Exploration

题意：

给n个点，m条单向边，投放机器人在任意点上，机器人可以沿着边的方向走，两个不同的机器人可能会在同一点相遇，问最少用多少个机器人可以访问所有的点。

题解：

最初读题不仔细，按最小路径覆盖做了，疯狂wa，后来发现题中提到了路径相交的可能，所以就不能直接求最小路径覆盖了。

最小路径覆盖的前提是用不相交的简单路径去覆盖,比如在下图中，我们可以知道只需要2个机器人就能完成任务，但是在下面的图中，最小路径覆盖是3，原因在于图中2号点那里有边相交的情况。

graph TD
1-->3
2-->3
3-->4
3-->5

至于求解该问题，我们只需要利用传递闭包，新增4条边：(1,4)，(1,5)，(2,4)，(2,5)，然后再求最小路径覆盖即可。

参考代码：

#include <cstdio>
#include <cstring>
using namespace std;
int n, m;
int match[509 * 2];
bool mp[509][509], used[509 * 2];

bool dfs(int u)
{
    for (int i = 1; i <= n; i++)
    {
        if (mp[u][i])
        {
            int v = i;
            if (!used[v])
            {
                used[v] = 1;
                if (match[v] == -1 || dfs(match[v]))
                {
                    match[v] = u;
                    return 1;
                }
            }
        }
    }
    return 0;
}
int MaxMatch()
{
    int sum = 0;
    memset(match, -1, sizeof(match));
    for (int i = 1; i <= n; i++)
    {
        memset(used, 0, sizeof(used));
        if (dfs(i))
            sum++;
    }
    return sum;
}
int main()
{
    while (scanf("%d%d", &n, &m) && (n || m))
    {
        if (!m)
        {
            printf("%d\n", n);
            continue;
        }
        memset(mp, 0, sizeof(mp));
        for (int i = 1; i <= m; i++)
        {
            int u, v;
            scanf("%d%d", &u, &v);
            mp[u][v] = 1;
        }
        for (int k = 1; k <= n; k++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    if (mp[i][k] && mp[k][j])
                        mp[i][j] = 1;
        int ans = MaxMatch();
        printf("%d\n", n - ans);
    }
    return 0;
}