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
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N = 40;
7int n,m,k;
8bool hole[N][N];
9int f1[N][N],f2[N][N];
10int tot1,tot2;
11int head[N*N*2];
12int cnt;
13bool vis[N*N*2];
14int link[N*N*2];
15struct Edge
16{
17 int v;
18 int nxt;
19}edge[2*N*N];
20void addedge( int u,int v)
21{
22 edge[cnt].v = v;
23 edge[cnt].nxt = head[u];
24 head[u] = cnt;
25 cnt++;
26}
1bool dfs( int u)
2{
3 for ( int i = head[u] ; i!=-1 ; i = edge[i].nxt)
4 {
5 int v = edge[i].v;
6 if (vis[v]) continue;
7 vis[v] = true;
8 if (link[v]==-1||dfs(link[v]))
9 {
10 link[v] = u;
11 return true;
12 }
13 }
14 return false;
15}
1int hung()
2{
3 ms(link,-1);
4 int res = 0;
5 for ( int i = 1 ; i <= tot1 ; i++)
6 {
7 ms(vis,false);
8 if (dfs(i)) res++;
9 }
return res; //无相边/2,一对匹配占两个格子，×2，抵消了。。
1}
2int main()
3{
4 #ifndef ONLINE_JUDGE
5 freopen("code/in.txt","r",stdin);
6 #endif
7 scanf("%d%d%d",&n,&m,&k);
8 ms(hole,false);
9 ms(head,-1);
10 for ( int i = 1 ; i <= k ; i++)
11 {
12 int x,y;
13 scanf("%d%d",&x,&y);
14 swap(x,y);
15 hole[x][y] = true;
16 }
1 if ((n*m-k)%2==1)
2 {
3 puts("NO");
4 return 0;
5 }
6 tot1 = tot2 = 0 ; //根据奇偶性划分集合。
7 for ( int i = 1 ; i <= n ; i++)
8 for ( int j = 1 ; j <= m ; j++)
9 if (!hole[i][j])
10 {
11 if ((i+j)%2==0)
12 {
13 f1[i][j]=++tot1;
14 }
15 else
16 {
17 f2[i][j]=++tot2;
18 }
19 }
1 cnt = 0 ;
2 for ( int i = 1 ; i <= n ; i++)
3 for ( int j = 1 ; j <= m ; j++)
4 {
5 if (!hole[i][j]&&j+1<=m&&!hole[i][j+1])
6 {
7 int u = (i+j)%2==0?f1[i][j]:f2[i][j];
8 int v = (i+j+1)%2==0?f1[i][j+1]:f2[i][j+1];
9 if ((i+j)%2==1) swap(u,v);
10 addedge(u,v); // 保证是f1的点连向f2的点。
11 // addedge(v,u);
12 }
13 if (!hole[i][j]&&i+1<=n&&!hole[i+1][j])
14 {
15 int u = (i+j)%2==0?f1[i][j]:f2[i][j];
16 int v = (i+j+1)%2==0?f1[i+1][j]:f2[i+1][j];
17 if ((i+j)%2==1) swap(u,v);
18 addedge(u,v); //无向图
19 // addedge(v,u);
20 }
21 }
1 int ans = hung();
2// cout<<"ans:"<<ans<<endl;
3 if (ans*2+k==m*n)
4 {
5 puts("YES");
6 }
7 else
8 {
9 puts("NO");
10 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}