poj 2446 Chessboard (二分匹配)

Chessboard
Time Limit: 2000MS   Memory Limit: 65536K
Total Submissions: 12800   Accepted: 4000

Description

Alice and Bob often play games on chessboard. One day, Alice draws a board with size M * N. She wants Bob to use a lot of cards with size 1 * 2 to cover the board. However, she thinks it too easy to bob, so she makes some holes on the board (as shown in the figure below). 
poj 2446 Chessboard (二分匹配)
We call a grid, which doesn’t contain a hole, a normal grid. Bob has to follow the rules below: 
1. Any normal grid should be covered with exactly one card. 
2. One card should cover exactly 2 normal adjacent grids.

Some examples are given in the figures below: 
poj 2446 Chessboard (二分匹配) 
A VALID solution.
poj 2446 Chessboard (二分匹配) 
An invalid solution, because the hole of red color is covered with a card.
poj 2446 Chessboard (二分匹配) 
An invalid solution, because there exists a grid, which is not covered.
Your task is to help Bob to decide whether or not the chessboard can be covered according to the rules above.

Input

There are 3 integers in the first line: m, n, k (0 < m, n <= 32, 0 <= K < m * n), the number of rows, column and holes. In the next k lines, there is a pair of integers (x, y) in each line, which represents a hole in the y-th row, the x-th column.

Output

If the board can be covered, output "YES". Otherwise, output "NO".

Sample Input

4 3 2
2 1
3 3

Sample Output

YES

Hint

poj 2446 Chessboard (二分匹配) 
A possible solution for the sample input.

Source

POJ Monthly,charlescpp

和 hdu 1507类似,构无向图然后判断匹配数是否等于合法的格数。

心算32*32错了= = RE了两次,开始以为32*32是90+,第二次以为是900+,笔算后才知道是1024..

 //224K    125MS    C++    1731B    2014-06-10 12:44:41
#include<iostream>
#include<vector>
#define N 1050
using namespace std;
vector<int>V[N];
int match[N];
int vis[N];
int g[][];
int dfs(int u)
{
for(int i=;i<V[u].size();i++){
int v=V[u][i];
if(!vis[v]){
vis[v]=;
if(match[v]==- || dfs(match[v])){
match[v]=u;
return ;
}
}
}
return ;
}
int hungary(int n)
{
int ret=;
memset(match,-,sizeof(match));
for(int i=;i<=n;i++){
memset(vis,,sizeof(vis));
ret+=dfs(i);
}
return ret;
}
int main(void)
{
int n,m,k,x,y;
while(scanf("%d%d%d",&n,&m,&k)!=EOF)
{
memset(g,,sizeof(g));
for(int i=;i<N;i++) V[i].clear();
for(int i=;i<k;i++){
scanf("%d%d",&y,&x);
g[x-][y]=;
}
int map[N]={},pos=;
for(int i=;i<n;i++)
for(int j=;j<=m;j++)
if(!g[i][j]){
if(!map[i*m+j]) map[i*m+j]=++pos;
int u=map[i*m+j];
if(j<m && !g[i][j+]){
if(!map[i*m+j+]) map[i*m+j+]=++pos;
V[u].push_back(map[i*m+j+]);
V[map[i*m+j+]].push_back(u);
}
if(i<n- && !g[i+][j]){
if(!map[(i+)*m+j]) map[(i+)*m+j]=++pos;
V[u].push_back(map[(i+)*m+j]);
V[map[(i+)*m+j]].push_back(u);
}
}
//printf("%d\n",pos);
if(hungary(pos)==pos) puts("YES");
else puts("NO");
}
return ;
}
上一篇:ubuntu pip install MySQL-python mysql_config not found


下一篇:数据结构Python版练习题(一)