POJ 3020 Antenna Placement(二分图的最大匹配)
http://poj.org/problem?id=3020
题意:
一个矩形中，有N个城市’*’，其余网格都为'o'表示空地。现在这n个城市都要覆盖无线，若放置一个基站，那么它至多可以覆盖相邻的两个城市。
问至少放置多少个基站才能使得所有的城市都覆盖无线？这个基站的位置可以任意放,不管当前位置是’*’还是’o’.
分析:
一直就感觉这道题很相似,跟以前做的网格用1*2小矩阵覆盖的题目类似。
首先本题既不是二分图的最小边覆盖，也不是DAG最小路径覆盖问题，只不过是二分图的最大匹配问题而已。
我们把图中的每个’*’都标号，分别放到二分图的左右点集去。(行号+列号==偶数的放左边,行号+列号==奇数的放右边)。 如果存在两个相邻的’*’，那么就在他们之间连一条无向边(这条边肯定是连接左右点集的,因为网格是天然二分的)。这样就行了一个新的二分图G。
首先我们要知道对于任意一个’*’来说，它或者由一个基站(1*2矩形)单独覆盖(即该矩形实际只能算覆盖了1个’*’)，或者由一个基站通过覆盖另一个与其相邻的’*’来顺便把它覆盖(即该矩形有效覆盖了2个相邻的’*’)。
既然总的’*’是固定的，那么我们用的基站数目最多不会超过“*”的数目。所以我们想要用基站的数目最少，必须使得实际有效覆盖两个’*’的基站数目最多(想想对不对)。那么实际有效覆盖两个’*’的基站数目最多有多少个呢? 这个数目正好等于我们所建二分图的最大匹配边数。(因为二分图的每条匹配边就是一条正好有效覆盖两个相邻’*’的矩形)。既然这样 我们最终需要的基站总数= ‘*’的总数-最大匹配边数(因为每条匹配边正好覆盖了2个’*’)
AC代码:
#include <cstdio> #include <algorithm> #include <iostream> #include <cstring> #include<stack> #include<vector> using namespace std; const int maxn=500+10; struct Max_Match { int n,m; vector<int>g[maxn]; bool vis[maxn]; int left[maxn]; void init(int n,int m) { this->n=n; this->m=m; for(int i=1;i<=n;i++) g[i].clear(); memset(left,-1,sizeof left); } bool match(int u) { for(int i=0;i<g[u].size();i++) { int v=g[u][i]; if(!vis[v]) { vis[v]=true; if(left[v]==-1||match(left[v])) { left[v]=u; return true; } } } return false; } int solve() { int ans=0; for(int i=1;i<=n;i++) { memset(vis,false,sizeof vis); if(match(i))ans++; } return ans; } }MM; char maps[50][50]; int go[4][2]={1,0,-1,0,0,1,0,-1}; int main() { int n,m; int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); MM.init(n*m,n*m); int cnt=0; for(int i =0;i<n;i++) { scanf("%s",maps[i]); for(int j=0;j<m;j++) if(maps[i][j]=='*')cnt++; } //cout<<cnt<<"*/*"<<endl; for(int i=0;i<n;i++) for(int j=0;j<m;j++) { if((i+j)%2==0&&maps[i][j]=='*') { for(int k=0;k<4;k++) { int x=i+go[k][0]; int y=j+go[k][1]; if(x>=0&&x<n&&y>=0&&y<m&&maps[x][y]=='*') { MM.g[i*m+j+1].push_back(x*m+y+1); } } } } printf("%d\n",cnt-MM.solve()); } }
