【最小点覆盖】POJ 2226：Muddy Fields

一、题目内容

POJ 2226 原题地址

二、题意解释

告诉你一个矩阵，让你用1 * x (x 为任意值） 的木板去铺符号* 可以覆盖 问最少多少木板能够把所有的*覆盖掉

三、代码及注释

#include<stdio.h> #include<iostream> #include<string.h> using namespace std; const int maxn=2505; int g[maxn][maxn]; int girl[maxn],used[maxn];//girl表示女生喜欢的男生，used表示女生是否被匹配到 int n,m; int n1,n2; int a[55][55]; int b[55][55]; char mapp[55][55]; bool Find(int x) { for (int i = 1; i <= n2; i++) { // n 为女生的个数，这道题和男生个数一样 if (g[x][i] && !used[i]) { // x 和 i 是互相喜欢的（别忘了这个），并且这个妹子名花无主 used[i] = 1;// 表示这个妹子配对上 if (girl[i] == 0 || Find(girl[i])) { // 如果这个妹子没有匹配上人 或者 这个男生可以喜欢别人 girl[i] = x;// i 个女生就和 x 配对上 return true; } } } return false; } //建立二分图函数 void Build(){ n1=0;n2=0; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); //按照列给同一列的编相同的号，并作为二分图左边集合 for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(mapp[i][j]=='*'){ if(mapp[i][j-1]=='*') a[i][j]=a[i][j-1]; else a[i][j]=++n1; } } } //按照行给同一行的编相同的号，并作为二分图右边集合 for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(mapp[i][j]=='*'){ if(mapp[i-1][j]=='*') b[i][j]=b[i-1][j]; else b[i][j]=++n2; g[a[i][j]][b[i][j]]=1; } } } } int main(){ scanf("%d%d",&n,&m); memset(girl, 0, sizeof(girl)); memset(g, 0, sizeof(g)); for(int i=0;i<n;i++){ scanf("%s",&mapp[i]); } Build(); int ans=0; for(int i=1;i<=n1;i++){//枚举集合A中的点，n为集合A中点的个数，即男生的个数 memset(used,0,sizeof(used));//这里每次都需要全部清0 if(Find(i))ans++;//注意这一步用来得到答案 } printf("%d\n",ans); return 0; }