POJ 2446 Chessboard 二分图的最大匹配 <建图>

题意：

给一 n*m 的棋盘..其中挖了几个洞<闲的没事了..>

在木有洞的相邻两个格涂颜色..

问能不能都涂上..

这就是能涂上的..如果能就输出YES 不能就NO

思路：

※ 很特别的建图方法..因为左右相邻的两个格子的i+j的奇偶性肯定不一样..

所以就以 i+j 的奇偶性来分出两个集合..成为二分图..

i+j 是奇数为一个集合..i+j 是偶数为一个集合..

然后利用匈牙利算法..求出最大匹配数..

最大匹配数正好是未挖洞的格子个数的一半就证明是YES..

Tips：

先是都初始化为-1 如果是挖洞了的就变成0

然后根据 i + j 奇偶性给每个格子编号..即第几个奇数格子..第几个偶数格子..

然后用一个图G..根据每个格子的上下左右四个格子如果没被挖洞就一定是和它奇偶性相反来连线建图..

Code：

View Code

 1 #include <stdio.h>
 2 #include <cstring>
 3 #define clr(x) memset(x, 0, sizeof(x))
 4 
 5 int v1, v2;
 6 bool G[1500][1500];
 7 bool vis[1500];
 8 int link[1500];
 9 int sum;
10 
11 bool dfs(int x)
12 {
13     for(int y = 1; y <= v2; ++y)
14         if(G[x][y] && !vis[y]){
15             vis[y] = true;
16             if(link[y] == 0 || dfs(link[y])){
17                 link[y] = x;
18                 return true;
19             }
20         }
21     return false;
22 }
23 
24 void search()
25 {
26     clr(link);
27     sum = 0;
28     for(int x = 1; x <= v1; ++x){
29         clr(vis);
30         if(dfs(x))
31             sum++;
32     }
33     return;
34 }
35 
36 
37 int main()
38 {
39 
40     int i, j;
41     int arr[35][35];
42     int m, n, k;
43     int x, y;
44     int tmpn, tmpm;
45     while(scanf("%d %d %d", &n, &m, &k) != EOF)
46     {
47         memset(arr, -1, sizeof(arr));
48         clr(G);
49         v1 = v2 = 0;
50 
51         for(i = 0; i < k; ++i){
52             scanf("%d %d", &x, &y);
53             arr[y][x] = 0;///!!!
54         }
55 
56         if((n*m-k)%2 != 0){
57             printf("NO\n");
58             continue;
59         }
60 
61         for(i = 1; i <= n; ++i)
62         for(j = 1; j <= m; ++j){
63             if(arr[i][j] == -1)
64             {
65                 if((i+j)%2 == 1)
66                     arr[i][j] = ++v1;
67                 else
68                     arr[i][j] = ++v2;
69             }
70         }
71 
72         for(i = 1; i <= n; ++i)
73         for(j = 1; j <= m; ++j){
74             if((i+j)%2 == 0 || arr[i][j] < 1) continue;
75             if(arr[i-1][j] >= 1)
76                 G[arr[i][j]][arr[i-1][j]] = true;
77             if(arr[i+1][j] >= 1)
78                 G[arr[i][j]][arr[i+1][j]] = true;
79             if(arr[i][j-1] >= 1)
80                 G[arr[i][j]][arr[i][j-1]] = true;
81             if(arr[i][j+1] >= 1)
82                 G[arr[i][j]][arr[i][j+1]] = true;
83         }
84         search();
85 //printf("%d\n", sum);
86         if(sum == (n*m-k)/2) puts("YES");
87         else puts("NO");
88     }
89 
90 
91     return 0;
92 }