poj 2446 Chessboard (匈牙利算法)

poj 2446 题目链接 题意：一个nm的矩形方格里，有k个坏点，然后问能否用12的矩形块将矩形方格填满。坏点不能填，小的矩形块不能重叠，不能超出边界。不能有好点没有被填。

思路：乍一看没什么好的思路。。。然后发现小的矩形块只能有两种放置方法（横着放，竖着放） 可能我们对于第i个，可以横着放，也可以竖着放，但是可能某种方案使得后面的某一块没办法放置，因此我们需要反过来调整第i块的放法。  这个过程似乎和二分图匹配有点类似。。？  那到底有没有相似点呢。。。又如何划分集合呢。。。？

如果每个小方格看做点，能不能填满，其实就等价与这些点的最大匹配数×2+坏点数=mn是否成立。。。那如何划分集合呢。。。？ 我们可以根据点的坐标的奇偶性划分集合。。。因为小矩形块是21的，所以容易知道，每块矩形块放置的两个点一定属于不同的集合。。这样就满足了二分图匹配问题的模型。。。

然后匈牙利搞之。

这题一开始WA了。。WA在没有注意到一个小细节，使得连边的时候，有的是左点指向右点，而有的连成了右点指向左点。

/* ***********************************************
Author :111qqz
Created Time :2016年05月25日 星期三 20时19分04秒
File Name :code/poj/2446.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N = 40;
int n,m,k;
bool hole[N][N];
int f1[N][N],f2[N][N];
int tot1,tot2;
int head[N*N*2];
int cnt;
bool vis[N*N*2];
int link[N*N*2];
struct Edge
{
    int v;
    int nxt;
}edge[2*N*N];
void addedge( int u,int v)
{
    edge[cnt].v = v;
    edge[cnt].nxt = head[u];
    head[u] = cnt;
    cnt++;
}

bool dfs( int u)
{
    for ( int i = head[u] ; i!=-1 ; i = edge[i].nxt)
    {
	int v = edge[i].v;
	if (vis[v]) continue;
	vis[v] = true;
	if (link[v]==-1||dfs(link[v]))
	{
	    link[v] = u;
	    return true;
	}
    }
    return false;
}

int hung()
{
    ms(link,-1);
    int res = 0;
    for ( int i = 1 ; i <= tot1 ; i++)
    {
	ms(vis,false);
	if (dfs(i)) res++;
    }

    return res; //无相边/2,一对匹配占两个格子，×2，抵消了。。

}
int main()
{
	#ifndef  ONLINE_JUDGE 
	freopen("code/in.txt","r",stdin);
  #endif
	scanf("%d%d%d",&n,&m,&k);
	ms(hole,false);
	ms(head,-1);
	for ( int i = 1 ; i <= k ; i++)
	{
	    int x,y;
	    scanf("%d%d",&x,&y);
	    swap(x,y);
	    hole[x][y] = true;
	}
	
	if ((n*m-k)%2==1)
	{
	    puts("NO");
	    return 0;
	}
	tot1 =  tot2 = 0 ;                       //根据奇偶性划分集合。
	for ( int i = 1 ; i <= n ; i++)
	    for ( int j = 1 ; j <= m ; j++)
		if (!hole[i][j])
		{
		    if ((i+j)%2==0)
		    {
			f1[i][j]=++tot1;
		    }
		    else
		    {
			f2[i][j]=++tot2;
		    }
		}
	
	cnt = 0 ;
	for ( int i = 1 ; i <= n ; i++)
	    for ( int j = 1 ; j <= m ; j++)
	    {
		if (!hole[i][j]&&j+1<=m&&!hole[i][j+1])
		{
		    int u = (i+j)%2==0?f1[i][j]:f2[i][j];
		    int v = (i+j+1)%2==0?f1[i][j+1]:f2[i][j+1];
		    if ((i+j)%2==1) swap(u,v);
		    addedge(u,v);  // 保证是f1的点连向f2的点。
		  //  addedge(v,u);
		}
		if (!hole[i][j]&&i+1<=n&&!hole[i+1][j])
		{
		    int u = (i+j)%2==0?f1[i][j]:f2[i][j];
		    int v = (i+j+1)%2==0?f1[i+1][j]:f2[i+1][j];
		    if ((i+j)%2==1) swap(u,v); 
		    addedge(u,v);  //无向图
		  //  addedge(v,u);
		}
	    }

	int ans = hung();
//	cout<<"ans:"<<ans<<endl;
	if (ans*2+k==m*n)
	{
	    puts("YES");
	}
	else
	{
	    puts("NO");
	}

  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}