POJ2446 Chessboard 最大匹配

　　昨天没有搞出来，今天汇编课想出来了，发现还是水水的，昨天估计是受到前面两题的影响，一直把思考方向搞错了= =||。

　　题目要求用1*2的卡片覆盖整个区域，而且要恰好完全覆盖，不能有重叠。仔细发现，每个格子要么是被横着的1*2的卡片覆盖，要么是竖着的覆盖，而且每个只能和周围上下左右的四个格子同时覆盖，那么这里就可以抽象出每个格子和周围四个格子的匹配问题，就像国际象棋的黑白相间的格子一样。

　　例如（0可放，-1不可放）：

　　　　　　0 -1 0　　　　　　　　　　　　1 0 2　　　　　　0 0 0

　　　　　　0 0 0 ——————> 　　 0 3 0　　　　　　1 0 2

　　　　　　0 0 -1　　　　　　　　　　　　4 0 0　　　　　　0 3 0

　　　　　　0 0 0　　　　　　　　　　　　0 5 0　　　　　　4 0 5

　　　　初始的棋盘　　　　　　　　　　　X集合 Y集合

　　那么就是求X集合和Y集合的最大匹配，如果最大匹配是完备匹配，那么就是YES了，否则就是NO。

 1 //STATUS:G++_AC_188MS_1660KB
 2 #include<stdio.h>
 3 #include<stdlib.h>
 4 #include<string.h>
 5 #include<math.h>
 6 #include<iostream>
 7 #include<string>
 8 #include<algorithm>
 9 #include<vector>
10 #include<queue>
11 #include<stack>
12 #include<map>
13 using namespace std;
14 #define LL long long
15 #define Max(a,b) ((a)>(b)?(a):(b))
16 #define Min(a,b) ((a)<(b)?(a):(b))
17 #define mem(a,b) memset(a,b,sizeof(a))
18 #define lson l,mid,rt<<1
19 #define rson mid+1,r,rt<<1|1
20 const int MAX=35,INF=0x3f3f3f3f;
21 
22 int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
23 int w[MAX*MAX>>1][MAX*MAX>>1],g[MAX][MAX],y[MAX*MAX],vis[MAX*MAX];
24 int n,m,k,coux,couy;
25 
26 void getg()
27 {
28     int i,j,flag=0,k,ni,nj;
29     mem(w,0);
30     for(i=0;i<n;i++)
31         for(j=flag^=1;j<m;j+=2)
32             if(g[i][j]!=-1)g[i][j]=++couy;
33     flag=1;
34     for(i=0;i<n;i++){
35         for(j=flag^=1;j<m;j+=2){
36             if(g[i][j]!=-1){
37                 ++coux;
38                 for(k=0;k<4;k++){
39                     ni=i+dx[k],nj=j+dy[k];
40                     if(ni>=0&&ni<n && nj>=0&&nj<m && g[ni][nj]!=-1){
41                         w[coux][g[ni][nj]]=1;
42                     }
43                 }
44             }
45         }
46     }
47 }
48 
49 int dfs(int u)
50 {
51     int v;
52     for(v=1;v<=couy;v++){
53         if(w[u][v] && !vis[v]){
54             vis[v]=1;
55             if(!y[v] || dfs(y[v])){
56                 y[v]=u;
57                 return 1;
58             }
59         }
60     }
61     return 0;
62 }
63 
64 int main()
65 {
66   //  freopen("in.txt","r",stdin);
67     int i,j,a,b,ok;
68     while(~scanf("%d%d%d",&n,&m,&k))
69     {
70         mem(g,0);
71         mem(y,0);
72         coux=couy=0;
73         ok=1;
74         for(i=0;i<k;i++){
75             scanf("%d%d",&a,&b);
76             g[b-1][a-1]=-1;
77         }
78 
79         if(!(k&1)){
80             getg();
81             if(coux==couy){
82                 for(i=1;i<=coux;i++){
83                     mem(vis,0);
84                     if(!dfs(i)){
85                         ok=0;
86                         break;
87                     }
88                 }
89             }
90             else ok=0;
91         }
92         else ok=0;
93 
94         printf("%s\n",ok?"YES":"NO");
95     }
96     return 0;
97 }