当前位置：网站首页>POJ2594 Treasure Exploration【二分图最小路径覆盖】【Floyd】

POJ2594 Treasure Exploration【二分图最小路径覆盖】【Floyd】

2022-07-27 12:36:00 【51CTO】

题目链接：

http://poj.org/problem?id=2594

题目大意：

给你N个地点，M条有向边，已知构成的图是有向无环图。现在要在地点上放机器人通过M

条边来遍历N个地点，问：最少需要多少个机器人可以遍历N个地点。

思路：

这是一道求最小路径覆盖的题目。和一般最小路径覆盖的题目不一样的地方是：这里的点可

以重复遍历。也就是可以有两个及以上的机器人经过同一个点。那么，先建立一个二分图，

两边都为N个地点。然后在原图的基础上，用Floyd求一次传递闭包，也就是如果点i可以到达

点j，而点j可以到达点k，那么可以当做点i可以直接跳过点j而到达点k，就可以建立一条有向

边(i，k)。建好图后，就是一般的二分图最小路径覆盖的问题了。而二分图最小路径覆盖 =

点数 - 二分图最大匹配，用匈牙利算法求出二分图最大匹配就可以了。

AC代码：

       
       #include<iostream>
       
       #include<algorithm>
       
       #include<cstdio>
       
       #include<cstring>
       
       using 
       
       namespace 
       
       std;
       
       const 
       
       int 
       
       MAXN 
       
       = 
       
       550;
       
       bool 
       
       Map[
       
       MAXN][
       
       MAXN],
       
       Mask[
       
       MAXN];
       
       int 
       
       NX,
       
       NY;
       
       int 
       
       cx[
       
       MAXN],
       
       cy[
       
       MAXN];
       
       void 
       
       Floyd(
       
       int 
       
       N)       
       
       //求传递闭包
       
{
       
       for(
       
       int 
       
       k 
       
       = 
       
       1; 
       
       k 
       
       <= 
       
       N; 
       
       ++
       
       k)
       
    {
       
       for(
       
       int 
       
       i 
       
       = 
       
       1; 
       
       i 
       
       <= 
       
       N; 
       
       ++
       
       i)
       
        {
       
       for(
       
       int 
       
       j 
       
       = 
       
       1; 
       
       j 
       
       <= 
       
       N; 
       
       ++
       
       j)
       
            {
       
       if(
       
       i 
       
       != 
       
       j 
       
       && 
       
       Map[
       
       i][
       
       k] 
       
       && 
       
       Map[
       
       k][
       
       j])
       
       Map[
       
       i][
       
       j] 
       
       = 
       
       1;
       
            }
       
        }
       
    }
       
}
       
       int 
       
       FindPath(
       
       int 
       
       u)
       
{
       
       for(
       
       int 
       
       i 
       
       = 
       
       1; 
       
       i 
       
       <= 
       
       NY; 
       
       ++
       
       i)
       
    {
       
       if(
       
       Map[
       
       u][
       
       i] 
       
       && 
       
       !
       
       Mask[
       
       i])
       
        {
       
       Mask[
       
       i] 
       
       = 
       
       1;
       
       if(
       
       cy[
       
       i] 
       
       == 
       
       -
       
       1 
       
       || 
       
       FindPath(
       
       cy[
       
       i]))
       
            {
       
       cy[
       
       i] 
       
       = 
       
       u;
       
       cx[
       
       u] 
       
       = 
       
       i;
       
       return 
       
       1;
       
            }
       
        }
       
    }
       
       return 
       
       0;
       
}
       
       int 
       
       MaxMatch()  
       
       //二分图最大匹配
       
{
       
       for(
       
       int 
       
       i 
       
       = 
       
       1; 
       
       i 
       
       <= 
       
       NX; 
       
       ++
       
       i)
       
       cx[
       
       i] 
       
       = 
       
       -
       
       1;
       
       for(
       
       int 
       
       i 
       
       = 
       
       1; 
       
       i 
       
       <= 
       
       NY; 
       
       ++
       
       i)
       
       cy[
       
       i] 
       
       = 
       
       -
       
       1;
       
       int 
       
       res 
       
       = 
       
       0;
       
       for(
       
       int 
       
       i 
       
       = 
       
       1; 
       
       i 
       
       <= 
       
       NX; 
       
       ++
       
       i)
       
    {
       
       if(
       
       cx[
       
       i] 
       
       == 
       
       -
       
       1)
       
        {
       
       for(
       
       int 
       
       j 
       
       = 
       
       1; 
       
       j 
       
       <= 
       
       NY; 
       
       ++
       
       j)
       
       Mask[
       
       j] 
       
       = 
       
       0;
       
       res 
       
       += 
       
       FindPath(
       
       i);
       
        }
       
    }
       
       return 
       
       res;
       
}
       
       int 
       
       main()
       
{
       
       int 
       
       N,
       
       M,
       
       u,
       
       v;
       
       while(
       
       ~scanf(
       
       "%d%d",
       
       &
       
       N,
       
       &
       
       M) 
       
       && (
       
       N
       
       ||
       
       M))
       
    {
       
       memset(
       
       Map,
       
       0,
       
       sizeof(
       
       Map));
       
       for(
       
       int 
       
       i 
       
       = 
       
       1; 
       
       i 
       
       <= 
       
       M; 
       
       ++
       
       i)
       
        {
       
       scanf(
       
       "%d%d",
       
       &
       
       u,
       
       &
       
       v);
       
       Map[
       
       u][
       
       v] 
       
       = 
       
       1;
       
        }
       
       Floyd(
       
       N);
       
       NX 
       
       = 
       
       NY 
       
       = 
       
       N;
       
       printf(
       
       "%d\n",
       
       N 
       
       - 
       
       MaxMatch());
       
    }
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/ITCharge/5518560

当前位置：网站首页>POJ2594 Treasure Exploration【二分图最小路径覆盖】【Floyd】

POJ2594 Treasure Exploration【二分图最小路径覆盖】【Floyd】

边栏推荐

猜你喜欢

随机推荐