当前位置：网站首页>POJ2446 Chessboard【二分图最大匹配】

POJ2446 Chessboard【二分图最大匹配】

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

题目链接：

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

题目大意：

给一个N*M的矩阵，其中有K个地方有坑。告诉你这K个坑的位置，现在要用1*2的矩形板去覆盖

矩阵，不能覆盖有坑的地方。问：是否能把除了坑之外的地方全部覆盖掉，如果能，则输出"YES",

否则输出"NO"。

思路：

考虑到矩形板的规格是1*2，则相邻位置的(i，j)和(x，y)必然是(i+j)为奇数的话，(x+y)则为偶数。

(i+j)为偶数的话，(x+j)则为奇数。这样，就可以把图上的所有点分为横纵坐标相加为奇数的点和

横纵坐标相加为偶数的点。然后建立一个二分图，一边为奇数点，另一边为偶数点。如果能用矩

形板覆盖(即没有坑)，则在二分图上加边。然后求出二分图最大匹配ans，也就是最多能覆盖多少

矩形板。因为每个矩形板的规格是1*2，所以要判断是否能把除了坑之外的全部地方覆盖掉，只需

要判断ans*2 + K 是否等于M*N即可。

AC代码：

       
       #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://blog.51cto.com/ITCharge/5518557

当前位置：网站首页>POJ2446 Chessboard【二分图最大匹配】

POJ2446 Chessboard【二分图最大匹配】

边栏推荐

猜你喜欢

随机推荐