当前位置：网站首页>Poj1548 robots [bipartite graph minimum path coverage]

Poj1548 robots [bipartite graph minimum path coverage]

2022-07-27 13:04:00 【51CTO】

Topic link ：

The main idea of the topic ：

In a N*M(N <= 24,M <= 24) The figure of , There's a lot of rubbish , The robot cleaning garbage starts from the upper left corner . has

Know that robots can only clean garbage right or down , After cleaning up the garbage in a place, you can continue to clean it right or down

Other Waste . Finally run to (N,M) The position of ends . ask ： How many robots are needed at least , Can clean up all the garbage .

Ideas ：

There is no N and M Size , It just gives the location of the garbage . For input 0 0 Indicates the end of a group of data input . Build a structure

Body to store the coordinate value of garbage . Now let's build a bipartite graph , On both sides of the graph are garbage nodes , Traversal primitive , If garbage j stay

The garbage i In the lower right corner , will (i,j) Add to the bipartite graph , Finally, the problem becomes ： Find the minimum path cover of the bipartite graph . By two

Minimum path coverage of graph = points - Maximum matching of bipartite graph , The maximum matching of bipartite graph is obtained according to Hungarian algorithm , And then come to the conclusion .

AC Code ：

       
       #include<iostream>
       
       #include<algorithm>
       
       #include<cstdio>
       
       #include<cstring>
       
       using 
       
       namespace 
       
       std;
       
       const 
       
       int 
       
       MAXN 
       
       = 
       
       600;
       
       struct 
       
       Node
       
{
       
       int 
       
       x;
       
       int 
       
       y;
       
}
       
       Point[
       
       MAXN];
       
       bool 
       
       Map[
       
       MAXN][
       
       MAXN],
       
       Mask[
       
       MAXN];
       
       int 
       
       NX,
       
       NY;
       
       int 
       
       cx[
       
       MAXN],
       
       cy[
       
       MAXN];
       
       int 
       
       FindPath(
       
       int 
       
       u)
       
{
       
       for(
       
       int 
       
       i 
       
       = 
       
       0; 
       
       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 
       
       = 
       
       0; 
       
       i 
       
       < 
       
       NX; 
       
       ++
       
       i)
       
       cx[
       
       i] 
       
       = 
       
       -
       
       1;
       
       for(
       
       int 
       
       i 
       
       = 
       
       0; 
       
       i 
       
       < 
       
       NY; 
       
       ++
       
       i)
       
       cy[
       
       i] 
       
       = 
       
       -
       
       1;
       
       int 
       
       res 
       
       = 
       
       0;
       
       for(
       
       int 
       
       i 
       
       = 
       
       0; 
       
       i 
       
       < 
       
       NX; 
       
       ++
       
       i)
       
    {
       
       if(
       
       cx[
       
       i] 
       
       == 
       
       -
       
       1)
       
        {
       
       for(
       
       int 
       
       j 
       
       = 
       
       0; 
       
       j 
       
       < 
       
       NY; 
       
       ++
       
       j)
       
       Mask[
       
       j] 
       
       = 
       
       0;
       
       res 
       
       += 
       
       FindPath(
       
       i);
       
        }
       
    }
       
       return 
       
       res;
       
}
       
       int 
       
       main()
       
{
       
       int 
       
       id 
       
       = 
       
       0;
       
       while(
       
       scanf(
       
       "%d%d",
       
       &
       
       Point[
       
       id].
       
       x,
       
       &
       
       Point[
       
       id].
       
       y) 
       
       && (
       
       Point[
       
       id].
       
       x
       
       !=-
       
       1 
       
       && 
       
       Point[
       
       id].
       
       y
       
       !=-
       
       1))
       
    {
       
       id
       
       ++;
       
       while(
       
       scanf(
       
       "%d%d",
       
       &
       
       Point[
       
       id].
       
       x,
       
       &
       
       Point[
       
       id].
       
       y) 
       
       && (
       
       Point[
       
       id].
       
       x
       
       ||
       
       Point[
       
       id].
       
       y))
       
       id
       
       ++;
       
       memset(
       
       Map,
       
       0,
       
       sizeof(
       
       Map));
       
       for(
       
       int 
       
       i 
       
       = 
       
       0; 
       
       i 
       
       < 
       
       id; 
       
       ++
       
       i)
       
        {
       
       for(
       
       int 
       
       j 
       
       = 
       
       i
       
       +
       
       1; 
       
       j 
       
       < 
       
       id; 
       
       ++
       
       j)
       
            {
       
       if(
       
       Point[
       
       i].
       
       x 
       
       <= 
       
       Point[
       
       j].
       
       x 
       
       && 
       
       Point[
       
       i].
       
       y 
       
       <= 
       
       Point[
       
       j].
       
       y)
       
       Map[
       
       i][
       
       j] 
       
       = 
       
       1;
       
       else 
       
       if(
       
       Point[
       
       i].
       
       x 
       
       >= 
       
       Point[
       
       j].
       
       x 
       
       && 
       
       Point[
       
       i].
       
       y 
       
       >= 
       
       Point[
       
       j].
       
       y)
       
       Map[
       
       j][
       
       i] 
       
       = 
       
       1;
       
            }
       
        }
       
       NX 
       
       = 
       
       NY 
       
       = 
       
       id;
       
       printf(
       
       "%d\n",
       
       id
       
       -
       
       MaxMatch());
       
       id 
       
       = 
       
       0;
       
    }
       
       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://yzsam.com/2022/208/202207271233049209.html

当前位置：网站首页>Poj1548 robots [bipartite graph minimum path coverage]

Poj1548 robots [bipartite graph minimum path coverage]

边栏推荐

猜你喜欢

随机推荐