首页 > 代码库 > poj 3020 Antenna Placement（最大二分图匹配）
poj 3020 Antenna Placement（最大二分图匹配）
题意：
N行M列的矩阵，每个格子里不是 * 就是 O 。
* ：是一个利益点。
O：是一个空白点。
每次可以用一个圈覆盖相邻的两个*。（左右相邻或上下相邻）。
问最少需要多少个圈可以覆盖所有的*。
思路：
把每个格子变成一个数，总共有N*M个数。构造二分图，左右的数字都分别是1....N*M。
若两个*可以被一个圈覆盖，则将它们对应在左边、右边的点连上线。
答案即为：*的总数 - 最大二分匹配的值/2（因为有一半是对称的）。
代码：
int T,n,m;vector<int> graph[405];bool bmask[405];int cx[405],cy[405];char s[45][15];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,n*m) cx[i]=cy[i]=-1; rep(i,1,n*m) if(cx[i]==-1){ mem(bmask,false); ans+=findPath(i); } return ans;}int main(){ cin>>T; while(T--){ scanf("%d%d",&n,&m); rep(i,1,n*m) graph[i].clear(); int cc=0; rep(i,1,n) scanf("%s",s[i]); rep(i,1,n){ rep(j,0,m-1) if(s[i][j]==‘*‘){ int num=m*(i-1)+j+1; int u=i, v=j+1; if(v-1>=1 && s[u][j-1]==‘*‘) graph[num].push_back(num-1); if(v+1<=m && s[u][j+1]==‘*‘) graph[num].push_back(num+1); if(u-1>=1 && s[u-1][j]==‘*‘) graph[num].push_back(num-m); if(u+1<=n && s[u+1][j]==‘*‘) graph[num].push_back(num+m); ++cc; } } int dd=MaxMatch(); printf("%d\n",cc-dd/2); }}
poj 3020 Antenna Placement（最大二分图匹配）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。