poj2446Chessboard【矩阵建图+匈牙利】

大意：已知有一个n*m的矩阵现在用1 * 2 的小木块去铺这个矩阵，矩阵中的黑点表示陷阱不可以铺，问能不能把除了陷阱之外的所有各自都铺满

nm<= 32

分析：第一印象是状压dp但是n太大，

后来网二分图方向考虑，

首先要构建一个二分图，

怎么构建呢，

我们可以从二分图的定义入手---分成两个部分，并且每个部分内部相互之间不能有边

对于一个矩阵有这么一个现象将每个点坐标的横纵坐标相加，那么和为奇数的点之间肯定不会相连

我们把和为奇数的作为白棋，把和为偶数的作为黑棋

那么用二分图或网络流都可以来做了

代码：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 using namespace std;
  5 
  6 const int maxn = 33;
  7 const int INF = 1000000000;
  8 
  9 struct Node {
 10     int to;
 11     int next;
 12 }q[maxn * maxn * 2];
 13 
 14 int head[maxn * maxn * 2];
 15 int tot;
 16 int vis[maxn * maxn];
 17 int link[maxn * maxn];
 18 
 19 void AddEdge(int u, int v) {
 20     q[tot].to = v;
 21     q[tot].next = head[u];
 22     head[u] = tot ++;
 23 }
 24 
 25 int x_cnt;
 26 int X[maxn * maxn];
 27 
 28 bool find(int u) {
 29     for(int i = head[u]; i; i = q[i].next) {
 30         int v = q[i].to;
 31         if(!vis[v]) {
 32             vis[v] = 1;
 33             if(link[v] == -1 || find(link[v])) {
 34                 link[v] = u;
 35                 return true;
 36             }
 37         }
 38     }
 39     return false;
 40 }
 41 
 42 int KM() {
 43     int num = 0;
 44     memset(link, -1, sizeof(link));
 45     for(int i = 0; i < x_cnt; i++) {
 46         memset(vis, 0, sizeof(vis));
 47         if(find(X[i])) num++;
 48     }
 49     return num;
 50 }
 51 
 52 bool mat[maxn][maxn];
 53 
 54 int xx[4] = {0, 0, 1, -1};
 55 int yy[4] = {1, -1, 0, 0};
 56 
 57 int n, m;
 58 
 59 int change(int i, int j) {
 60     return m * (i - 1) + j;
 61 }
 62 
 63 bool check(int i, int j) {
 64     if(i >= 1 && i <= n && j >= 1 && j <= m && mat[i][j] == false) return true;
 65     return false;
 66 }
 67 
 68 int main() {
 69     int k; int x, y;
 70     //freopen("2446.txt","r",stdin);
 71     while(EOF != scanf("%d %d %d",&n, &m, &k)) {
 72         //if(n * m - k)
 73         int ans_cnt = n * m - k;
 74         if(ans_cnt & 1) {puts("NO"); continue;}
 75         ans_cnt /= 2;
 76         memset(mat, false, sizeof(mat));
 77         for(int i = 0; i < k; i++) {
 78             scanf("%d %d",&x, &y);
 79             mat[y][x] = true;
 80         }
 81         x_cnt = 0;
 82         tot = 1; memset(head, 0, sizeof(head));
 83         for(int i = 1; i <= n; i++) {
 84             for(int j = 1; j <= m; j++) {
 85                 if(!mat[i][j] && (i + j) % 2 == 1) {
 86                     int num_x = change(i, j);
 87                     X[x_cnt++] = num_x;
 88                     for(int k = 0; k < 4; k++) {
 89                         int tmpx = i + xx[k]; int tmpy = j + yy[k];
 90                         if(!check(tmpx, tmpy)) continue;
 91                         int num_y = change(tmpx, tmpy);
 92                         AddEdge(num_x, num_y);
 93                     }
 94                 }
 95             }
 96         }
 97         int ans = KM();
 98         if(ans == ans_cnt) puts("YES");
 99         else puts("NO");
100     }
101     return 0;
102 }

View Code