题目链接: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;
}