DLKKILL

DLKKILL's world

POJ - 3020 - Antenna Placement (二分图最小路径覆盖)

题目链接:POJ – 3020

题目大意:

一个矩形中,有N个城市’*’,现在这n个城市都要覆盖无线,若放置一个基站,那么它至多可以覆盖相邻的两个城市。

每个基站只能覆盖所在点已经他相邻的一个点(或上或左或下或右)
问至少放置多少个基站才能使得所有的城市都覆盖无线?

题目分析:

这是一个二分图的最小路径覆盖问题。

难点是如何建图。

对于每个城市给一个不同的编号,建立城市与城市直接的图(其中运用到了拆点的方法),然后进行二分图匹配。

无向二分图的最小路径覆盖 = 顶点数 – 最大二分匹配数/2 (除二是因为进行了拆点)

给出代码:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
using namespace std;
const int maxn=50;
const int maxn_m=50*50+10;
vector<string> maps;
int mark[maxn][maxn];
int cnt;
int n,m;
int walk[4][2]={1,0,-1,0,0,1,0,-1};
int g[maxn_m][maxn_m];
int vist[maxn_m];
int link[maxn_m];
void init()
{
    cnt=0;
 	maps.clear();
memset(mark,0,sizeof(mark));
memset(g,0,sizeof(g));
memset(link,0,sizeof(link));
}
bool dfs(int x)
{
for(int i=1;i<=cnt;i++)
{
if(g[x][i]&&!vist[i])
{
vist[i]=1;
if(link[i]==0||dfs(link[i])==true) //主要DFS传的参量应该是link[i],而不是i;
{
link[i]=x;
return true;
}
}
}
return false;
}
int search()
{
int ans=0;
for(int i=1;i<=cnt;i++)
{
memset(vist,0,sizeof(vist));
if(dfs(i))
ans++;
}
return ans;
}
int main()
{
   //for(int i=0;i<4;i++)
   // cout<<walk[i][0]<<" "<<walk[i][1]<<endl;
   int T;
   cin>>T;
   while(T--)
   {
       scanf("%d%d",&n,&m);
   init();
   for(int i=0;i<n;i++)
   {
   string s;
   cin>>s;
   maps.push_back(s);
   }
   for(int i=0;i<n;i++)
   {
   for(int j=0;j<m;j++)
   {
   if(maps[i][j]=='*')
   mark[i+1][j+1]=++cnt;
   else
   mark[i+1][j+1]=0;
   }
   }
   for(int i=1;i<=n;i++)
   {
   for(int j=1;j<=m;j++)
   {
   if(mark[i][j])
   {
   for(int k=0;k<4;k++)
   {
   int x=i+walk[k][0];
   int y=j+walk[k][1];
   if(mark[x][y])
   {
   int t1=mark[i][j];
   int t2=mark[x][y];
   g[t1][t2]=1;
   }
   }
   }
   }
   }
   /*for(int i=1;i<=cnt;i++)
       {
           for(int j=1;j<=cnt;j++)
             cout<<g[i][j];
           cout<<endl;
       }*/
   int ans=search();
   //cout<<ans<<endl;
   ans=(cnt-ans/2);
   cout<<ans<<endl;
  // for(int i=1;i<=cnt;i++)
      //  cout<<link[i]<<endl;
   }
   return 0;
}

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注