当前位置：网站首页>Poj2446 chessboard [maximum matching of bipartite graph]

Poj2446 chessboard [maximum matching of bipartite graph]

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

Topic link ：

The main idea of the topic ：

Give me a N*M Matrix , Among them is K There is a pit in one place . I'll tell you this K The location of the pit , Now use 1*2 Rectangular plate to cover

matrix , Do not cover places with pits . ask ： Can you cover all the places except the pit , If you can , The output "YES",

Otherwise output "NO".

Ideas ：

Considering that the specification of rectangular plate is 1*2, Then the adjacent position (i,j) and (x,y) It must be (i+j) For an odd number ,(x+y) It's an even number .

(i+j) Even numbers ,(x+j) Then it is an odd number . such , You can divide all the points on the graph into horizontal and vertical coordinates and add them to the sum of odd points

The horizontal and vertical coordinates are added to an even number of points . Then build a bipartite graph , One side is odd , The other side is an even number of points . If you can use moments

The shape plate covers ( That is, there is no pit ), Then add edges to the bipartite graph . Then find the maximum match of bipartite graph ans, That is, the maximum coverage

Rectangular plate . Because the specification of each rectangular plate is 1*2, So we should judge whether we can cover all the places except the pit , just

To judge ans*2 + K Is it equal to M*N that will do .

AC Code ：

       
       #include<iostream>
       
       #include<algorithm>
       
       #include<cstdio>
       
       #include<cstring>
       
       using 
       
       namespace 
       
       std;
       
       const 
       
       int 
       
       MAXN 
       
       = 
       
       33;
       
       const 
       
       int 
       
       MAXM 
       
       = 
       
       1100;
       
       bool 
       
       Map[
       
       MAXM][
       
       MAXM],
       
       Mask[
       
       MAXM];
       
       int 
       
       NX,
       
       NY;
       
       int 
       
       cx[
       
       MAXM],
       
       cy[
       
       MAXM];
       
       int 
       
       G[
       
       MAXN][
       
       MAXN];
       
       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;
       
       cy[
       
       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,
       
       K,
       
       u,
       
       v;
       
       while(
       
       ~scanf(
       
       "%d%d%d",
       
       &
       
       N,
       
       &
       
       M,
       
       &
       
       K))
       
    {
       
       memset(
       
       Map,
       
       0,
       
       sizeof(
       
       Map));
       
       memset(
       
       G,
       
       0,
       
       sizeof(
       
       G));
       
       for(
       
       int 
       
       i 
       
       = 
       
       1; 
       
       i 
       
       <= 
       
       K; 
       
       ++
       
       i)
       
        {
       
       scanf(
       
       "%d%d",
       
       &
       
       u,
       
       &
       
       v);
       
       G[
       
       u][
       
       v] 
       
       = 
       
       -
       
       1;
       
        }
       
       int 
       
       Num1,
       
       Num2;
       
       Num1 
       
       = 
       
       Num2 
       
       = 
       
       1;
       
       for(
       
       int 
       
       i 
       
       = 
       
       1; 
       
       i 
       
       <= 
       
       N; 
       
       ++
       
       i)
       
        {
       
       for(
       
       int 
       
       j 
       
       = 
       
       1; 
       
       j 
       
       <= 
       
       M; 
       
       ++
       
       j)
       
            {
       
       if(
       
       G[
       
       i][
       
       j] 
       
       == 
       
       0)
       
                {
       
       if((
       
       i
       
       +
       
       j)
       
       &
       
       1)
       
       G[
       
       i][
       
       j] 
       
       = 
       
       Num1
       
       ++;
       
       else
       
       G[
       
       i][
       
       j] 
       
       = 
       
       Num2
       
       ++;
       
                }
       
            }
       
        }
       
       for(
       
       int 
       
       i 
       
       = 
       
       1; 
       
       i 
       
       <= 
       
       N; 
       
       ++
       
       i)
       
        {
       
       for(
       
       int 
       
       j 
       
       = 
       
       1; 
       
       j 
       
       <= 
       
       M; 
       
       ++
       
       j)
       
            {
       
       if(
       
       G[
       
       i][
       
       j] 
       
       != 
       
       -
       
       1 
       
       && (
       
       i
       
       +
       
       j)
       
       &
       
       1)
       
                {
       
       if(
       
       G[
       
       i
       
       -
       
       1][
       
       j] 
       
       >= 
       
       1)
       
       Map[
       
       G[
       
       i
       
       -
       
       1][
       
       j]][
       
       G[
       
       i][
       
       j]] 
       
       = 
       
       1;
       
       if(
       
       G[
       
       i
       
       +
       
       1][
       
       j] 
       
       >= 
       
       1)
       
       Map[
       
       G[
       
       i
       
       +
       
       1][
       
       j]][
       
       G[
       
       i][
       
       j]] 
       
       = 
       
       1;
       
       if(
       
       G[
       
       i][
       
       j
       
       -
       
       1] 
       
       >= 
       
       1)
       
       Map[
       
       G[
       
       i][
       
       j
       
       -
       
       1]][
       
       G[
       
       i][
       
       j]] 
       
       = 
       
       1;
       
       if(
       
       G[
       
       i][
       
       j
       
       +
       
       1] 
       
       >= 
       
       1)
       
       Map[
       
       G[
       
       i][
       
       j
       
       +
       
       1]][
       
       G[
       
       i][
       
       j]] 
       
       = 
       
       1;
       
                }
       
            }
       
        }
       
       NX 
       
       = 
       
       Num1;
       
       NY 
       
       = 
       
       Num2;
       
       int 
       
       ans 
       
       = 
       
       MaxMatch();
       
       if(
       
       ans
       
       *
       
       2 
       
       + 
       
       K 
       
       == 
       
       M
       
       *
       
       N)
       
       printf(
       
       "YES\n");
       
       else
       
       printf(
       
       "NO\n");
       
    }
       
       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.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/208/202207271233049260.html

当前位置：网站首页>Poj2446 chessboard [maximum matching of bipartite graph]

Poj2446 chessboard [maximum matching of bipartite graph]

边栏推荐

猜你喜欢

随机推荐