首页 > 代码库 > poj2446Chessboard【矩阵建图+匈牙利】

poj2446Chessboard【矩阵建图+匈牙利】

2024-07-16 04:54:52   213人阅读

大意： 已知有一个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

 


联系
我们