題意： 給你一個N * M 的圖 ，然後用1 *2 的卡片去覆蓋，有些點是不能覆蓋的。問是否可以完全覆蓋
直接二分匹配找出最大匹配是否等於能覆蓋的點數。
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define PI acos(-1.0)
#define Max 2005
#define inf 1<<28
#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define Rep(i,s,t) for(int i=(s);i<=(t);++i)
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
using namespace std;
struct kdq
{
int e ,next ;
} ed[Max * 10] ;
int head[Max] , num ;
void add(int s ,int e )
{
ed[num].e = e ;
ed[num].next = head[s] ;
head[s] = num ++ ;
}
int link[Max] ;
bool vis[Max] ;
int dfs(int x )
{
for (int i = head[x] ; i != -1 ; i = ed[i].next )
{
int e = ed[i].e ;
if(!vis[e])
{
vis[e] = 1 ;
if(link[e] == -1 || dfs(link[e]))
{
link[e] = x ;
return 1 ;
}
}
}
return 0 ;
}
int Map[50][50] ;
int n ,m , k ;
int mx[4] = {0 ,0 , 1 ,-1} ;
int my[4] = {1 ,-1, 0 , 0} ;
int inmap(int x ,int y )
{
if(x >= 1 && x <= n &&y >= 1 && y <= m &&!Map[x][y])
return 1 ;
return 0 ;
}
int Mapnum[50][50] ;
int nn = 0 ;
void init()
{
mem(vis,0) ;
mem(head,-1) ;
mem(link,-1) ;
mem(Map,0) ;
mem(Mapnum,0) ;
nn = 0 ;
}
void build()
{
for (int i = 1 ; i <= n; i ++ )
{
for (int j = 1 ; j <= m ; j ++ )
{
if(Map[i][j] == 0)
Mapnum[i][j] = ++ nn ;
}
}
for (int i = 1 ; i <= n; i ++ )
{
for (int j = 1 ; j <= m ; j ++ )
{
if(!Map[i][j])
{
for (int k = 0 ; k < 4 ; k ++ )
{
int tx = i + mx[k] ;
int ty = j + my[k] ;
if(inmap(tx,ty))
{
add(Mapnum[i][j] ,Mapnum[tx][ty]) ;
}
}
}
}
}
}
int main()
{
while(cin >> n >> m >> k)
{
init() ;
int d = k ;
while(d -- )
{
int a , b ;
scanf("%d%d",&a,&b) ;
Map[b][a] = 1 ;
}
build() ;
int ans = 0 ;
for (int i = 1 ; i <= nn ; i ++ )
{
mem(vis,0) ;
ans += dfs(i) ;
}
int cnt = n * m - k ;
if((cnt & 1) || (ans != cnt ) )
cout <<"NO"<
else cout <<"YES"<
}
return 0;
