首页 > 代码库 > hdu 5093 Battle ships（二分图最大匹配）
hdu 5093 Battle ships（二分图最大匹配）
题意：
M*N的矩阵，每个格子上是三个之一：*、o、#。 (1 <= m, n <= 50)
*：海洋，战船可以停在上面。 o：浮冰，战船不可以停在上面 #：冰山，战船不可以停在上面。
限制：两艘战船不能处于同一行或同一列，除非它们之间有冰山挡着。
问最多可以停多少艘战船。
思路：
和二分图最小点覆盖那道经典题很相似。不过不是求最小点覆盖。
对于每一行，如果连续的一段只能放一艘战船，则将这一段视为同一个点。则每一行都被分为若干个小段，即若干个点。将这些点作为二分图的左部X集合。
对于每一列，同理。
对于（i,j）若这点可以放一艘战船，则将其对应在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); cin>>T; while(T--){ scanf("%d%d",&m,&n); rep(i,0,m-1) scanf("%s",mapp[i]); cc1=0, cc2=0; mem(row,0); mem(col,0); rep(i,0,m-1){ rep(j,0,n-1) temp[j]=mapp[i][j]; int p=0; while(p<n){ while(p<n&&temp[p]!=‘*‘) ++p; if(p<n) ++cc1; while(p<n&&temp[p]!=‘#‘) {row[i][p]=cc1; ++p;} } } rep(j,0,n-1){ rep(i,0,m-1) temp[i]=mapp[i][j]; int p=0; while(p<m){ while(p<m&&temp[p]!=‘*‘) ++p; if(p<m) ++cc2; while(p<m&&temp[p]!=‘#‘) {col[p][j]=cc2; ++p;} } } 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);}
hdu 5093 Battle ships（二分图最大匹配）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。