首页 > 代码库 > poj2226Muddy Fields【最小点覆盖(建图的思路比较好）】

poj2226Muddy Fields【最小点覆盖(建图的思路比较好）】

2024-07-18 06:22:28   216人阅读

大意：如下图告诉你一个矩阵，让你用1 * x (x 为任意值） 的木板去铺符号*  可以覆盖

问最少多少木板能够把所有的*覆盖掉

4 4*.*..******...*.

Boards 1, 2, 3 and 4 are placed as follows: 
1.2. 
.333 
444. 
..2. 
Board 2 overlaps boards 3 and 4.

分析：
题目要求是把所有的点都覆盖掉
回忆一下之前做过的
这种类型的大概就是二分图的最小点覆盖或者最小边覆盖
那么怎么建立二分图呢
因为X是个不确定值
所以我们尽量让X取值越大越好 
也就是说每一个横向或纵向的*区域都可以看做是一个联通块
那么只要把横向的连通块放在左集合，把纵向的连通块放在右集合 把点看左边
那么只要所有的边被覆盖则就是覆盖掉所有的*了
这样想来因为左右集合放的就是所求的连通块，那么只要求出最小点覆盖集即ok啦
最小点覆盖集 = 二分图最大匹配

代码：
 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <vector> 5 using namespace std; 6  7 const int maxn = 55; 8 int G[maxn * maxn / 2][maxn * maxn / 2]; 9 10 int vis[maxn * maxn / 2];11 int Link[maxn * maxn / 2];12 int n;13 bool Find(int u) {14     for(int i = 1; i <= n; i++) {15         if(G[u][i] && !vis[i]) {16             vis[i] = 1;17             if(Link[i] == -1 || Find(Link[i])) {18                 Link[i] = u;19                 return true;20             }21         }22     }23     return false;24 }25 26 int solve() {27     int cnt = 0;28     memset(Link, -1, sizeof(Link));29     for(int i = 1; i <= n; i++) {30         memset(vis, 0, sizeof(vis));31         if(Find(i)) cnt++;32     }33     return cnt;34 }35 36 char mat[maxn][maxn];37 int vis1[maxn][maxn], vis2[maxn][maxn];38 int main() {39     int m;40     for(int i = 0; i <= 50; i++) {41         mat[0][i] = mat[i][0] = ‘.‘;42     }43     while(EOF != scanf("%d %d",&n, &m)) {44         for(int i = 1; i <= n; i++) {45             for(int j = 1; j <= m; j++) {46                 scanf("\n%c",&mat[i][j]);47             }48         }49         int tot1 = 1; int tot2 = 1;50         memset(vis1, 0, sizeof(vis1)); memset(vis2, 0, sizeof(vis2));51         for(int i = 1; i <= n; i++) {52             for(int j = 1; j <= m; j++) {53                 if(mat[i][j] == ‘*‘) {54                     if(!vis1[i][j - 1]) {55                         vis1[i][j] = tot1++;56                     } else {57                         vis1[i][j] = vis1[i][j - 1];58                     }59                     if(!vis2[i - 1][j]) {60                         vis2[i][j] = tot2++;61                     } else {62                         vis2[i][j] = vis2[i - 1][j];63                     }64                 }65             }66         }67         memset(G, 0, sizeof(G));68         for(int i = 1; i <= n; i++) {69             for(int j = 1; j <= m; j++) {70                 if(mat[i][j] == ‘*‘) {71                     G[vis1[i][j]][vis2[i][j]] = 1;72                 }73             }74         }75         n = max(tot1, tot2);76         printf("%d\n",solve());77     }78     return 0;79 }
View Code

 


联系
我们