首页 > 代码库 > poj 2226 Muddy Fields（最小点覆盖）
poj 2226 Muddy Fields（最小点覆盖）
题意：
M*N的矩阵，每个格不是*就是#。 *代表水坑，#代表草地。
农民要每次可以用一块宽为1，长不限的木板去铺这个矩阵。要求这块木板不能覆盖草地。木板可以重复覆盖（即一块木板与另一块木板有交叉重叠的部分）。
问农民最少需要操作多少次可以覆盖所有的水坑。
思路 ：
与Battle Ships那题非常像，代码也几乎一样。
对于每一行，可以分成一段一段的水坑，将其视为一个一个点，作为左部X集合中的点。
对于每一列同理。
对于每一个水坑，将其看作一条线，将其在左部X集合中的位置和在右部Y集合中的位置连起来，代表这个水坑可以被那两块木板覆盖。
求二分图的最小点覆盖即可。（最小点覆盖：用最少的点【可以是左部的点，也可以是右部的点】，使得所有的边都至少有一个端点是被覆盖的）
代码：
int T,m,n;char mapp[55][55];char temp[55];int row[55][55], col[55][55];int cc1,cc2;int cx[2505], cy[2505];bool bmask[2505];vector<int> graph[2505];int findPath(int u){ int L=graph[u].size(); rep(i,0,L-1){ int v=graph[u][i]; if(!bmask[v]){ bmask[v]=true; if(cy[v]==-1||findPath(cy[v])){ cy[v]=u; cx[u]=v; return 1; } } } return 0;}int MaxMatch(){ int ans=0; rep(i,1,cc1) cx[i]=-1; rep(i,1,cc2) cy[i]=-1; rep(i,1,cc1) if(cx[i]==-1){ mem(bmask,false); ans+=findPath(i); } return ans;}int main(){ //freopen("test.in","r",stdin); while(scanf("%d%d",&m,&n)!=EOF){ rep(i,0,m-1) scanf("%s",mapp[i]); cc1=0, cc2=0; mem(row,0); mem(col,0); rep(i,0,m-1){ if(mapp[i][0]==‘*‘) row[i][0]=++cc1; rep(j,1,n-1) if(mapp[i][j]==‘*‘){ if(mapp[i][j-1]==‘*‘) row[i][j]=cc1; else row[i][j]=++cc1; } } rep(j,0,n-1){ if(mapp[0][j]==‘*‘) col[0][j]=++cc2; rep(i,1,m-1) if(mapp[i][j]==‘*‘){ if(mapp[i-1][j]==‘*‘) col[i][j]=cc2; else col[i][j]=++cc2; } } rep(i,1,cc1) graph[i].clear(); rep(i,0,m-1) rep(j,0,n-1) if(mapp[i][j]==‘*‘) graph[row[i][j]].push_back(col[i][j]); int dd=MaxMatch(); printf("%d\n",dd); } //fclose(stdin);}
poj 2226 Muddy Fields（最小点覆盖）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。