Note: This article is available in Chinese only. 本文暂无英文版本。
View original
poj 2446 题目链接 题意：一个nm的矩形方格里，有k个坏点，然后问能否用12的矩形块将矩形方格填满。坏点不能填，小的矩形块不能重叠，不能超出边界。不能有好点没有被填。
思路：乍一看没什么好的思路。。。然后发现小的矩形块只能有两种放置方法（横着放，竖着放） 可能我们对于第i个，可以横着放，也可以竖着放，但是可能某种方案使得后面的某一块没办法放置，因此我们需要反过来调整第i块的放法。 这个过程似乎和二分图匹配有点类似。。？ 那到底有没有相似点呢。。。又如何划分集合呢。。。？
如果每个小方格看做点，能不能填满，其实就等价与这些点的最大匹配数×2+坏点数=mn是否成立。。。那如何划分集合呢。。。？ 我们可以根据点的坐标的奇偶性划分集合。。。因为小矩形块是21的，所以容易知道，每块矩形块放置的两个点一定属于不同的集合。。这样就满足了二分图匹配问题的模型。。。
然后匈牙利搞之。
这题一开始WA了。。WA在没有注意到一个小细节，使得连边的时候，有的是左点指向右点，而有的连成了右点指向左点。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年05月25日 星期三 20时19分04秒
4File Name :code/poj/2446.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N = 40;
34int n,m,k;
35bool hole[N][N];
36int f1[N][N],f2[N][N];
37int tot1,tot2;
38int head[N*N*2];
39int cnt;
40bool vis[N*N*2];
41int link[N*N*2];
42struct Edge
43{
44 int v;
45 int nxt;
46}edge[2*N*N];
47void addedge( int u,int v)
48{
49 edge[cnt].v = v;
50 edge[cnt].nxt = head[u];
51 head[u] = cnt;
52 cnt++;
53}
54
55bool dfs( int u)
56{
57 for ( int i = head[u] ; i!=-1 ; i = edge[i].nxt)
58 {
59 int v = edge[i].v;
60 if (vis[v]) continue;
61 vis[v] = true;
62 if (link[v]==-1||dfs(link[v]))
63 {
64 link[v] = u;
65 return true;
66 }
67 }
68 return false;
69}
70
71int hung()
72{
73 ms(link,-1);
74 int res = 0;
75 for ( int i = 1 ; i <= tot1 ; i++)
76 {
77 ms(vis,false);
78 if (dfs(i)) res++;
79 }
80
81 return res; //无相边/2,一对匹配占两个格子，×2，抵消了。。
82
83}
84int main()
85{
86 #ifndef ONLINE_JUDGE
87 freopen("code/in.txt","r",stdin);
88 #endif
89 scanf("%d%d%d",&n,&m,&k);
90 ms(hole,false);
91 ms(head,-1);
92 for ( int i = 1 ; i <= k ; i++)
93 {
94 int x,y;
95 scanf("%d%d",&x,&y);
96 swap(x,y);
97 hole[x][y] = true;
98 }
99
100 if ((n*m-k)%2==1)
101 {
102 puts("NO");
103 return 0;
104 }
105 tot1 = tot2 = 0 ; //根据奇偶性划分集合。
106 for ( int i = 1 ; i <= n ; i++)
107 for ( int j = 1 ; j <= m ; j++)
108 if (!hole[i][j])
109 {
110 if ((i+j)%2==0)
111 {
112 f1[i][j]=++tot1;
113 }
114 else
115 {
116 f2[i][j]=++tot2;
117 }
118 }
119
120 cnt = 0 ;
121 for ( int i = 1 ; i <= n ; i++)
122 for ( int j = 1 ; j <= m ; j++)
123 {
124 if (!hole[i][j]&&j+1<=m&&!hole[i][j+1])
125 {
126 int u = (i+j)%2==0?f1[i][j]:f2[i][j];
127 int v = (i+j+1)%2==0?f1[i][j+1]:f2[i][j+1];
128 if ((i+j)%2==1) swap(u,v);
129 addedge(u,v); // 保证是f1的点连向f2的点。
130 // addedge(v,u);
131 }
132 if (!hole[i][j]&&i+1<=n&&!hole[i+1][j])
133 {
134 int u = (i+j)%2==0?f1[i][j]:f2[i][j];
135 int v = (i+j+1)%2==0?f1[i+1][j]:f2[i+1][j];
136 if ((i+j)%2==1) swap(u,v);
137 addedge(u,v); //无向图
138 // addedge(v,u);
139 }
140 }
141
142 int ans = hung();
143// cout<<"ans:"<<ans<<endl;
144 if (ans*2+k==m*n)
145 {
146 puts("YES");
147 }
148 else
149 {
150 puts("NO");
151 }
152
153 #ifndef ONLINE_JUDGE
154 fclose(stdin);
155 #endif
156 return 0;
157}