[最大独立集]ZOJ 1654.Place the Robots
(http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=654)
题目描述
罗伯特是一位著名的工程师。一天,他的老板给了他一项任务。任务背景如下:
给定一张由正方形块组成的地图。有三种街区:墙、草地和空地。他的老板想在地图上放置尽可能多的机器人。每个机器人都有一个激光武器,可以同时向四个方向(北、东、南、西)射击。机器人必须一直呆在最初放置它的地方,并且一直射击。激光束当然可以通过草地,但不能通过墙。机器人只能放在一个空块里。老板肯定不想看到机器人互相伤害。换句话说,除非两台机器人之间有一道墙,否则它们不能放在同一条线上(水平或垂直)。
既然你是如此聪明的程序员和罗伯特最好的朋友之一,他要求你帮助他解决这个问题。也就是说,给定地图的描述,计算可以放置在地图中的机器人的最大数量。
输入输出格式
输入格式
第一行包含一个整数T(T<=11),它是测试样例的数量。
对于每个测试用例,第一行包含两个整数m和n(1<=m,n<=50),它们是地图的行和列大小。接下来是m行,每行包含n个字符“#”、“*”或“o”,分别表示墙、草地和空地。
输出格式
对于每个测试样例,首先以一行的格式输出样例编号:“Case:id”,其中id是测试用例编号,从1开始计数。在第二行中,只输出可以放置在地图中的机器人的最大数量。
输入输出样例
输入样例#1:
2
4 4
o***
*###
oo#o
***o
4 4
#ooo
o#oo
oo#o
***#
输出样例#1:
Case :1
3
Case :2
5
题目解析
题目分析来自转载(https://blog.csdn.net/u014141559/article/details/44409255)
在问题的原型中,草地,墙这些信息不是本题所关心的,本题关心的只是空地和空地之间的联系。因此,很自然想到了下面这种简单的模型:以空地为顶点,在有冲突的空地间连边。
把所有的空地用数字标明,得到a图:
把所有有冲突的空地间用边连接后得到图(b):
于是,问题转化为求图的最大独立集问题:求最大顶点集合,集合中所有顶点互不连接(即互不冲突)。但是最大点独立集问题是一个NP 问题,没有有效的算法能求解。
—————————————————————————————————————————————————————
将每一行被墙隔开、且包含空地的连续区域称作“块”。显然,在一个块之中,最多只能放一个机器人。把这些块编上号,如图7.25(a)所示。需要说明的是,最后一行,即第4 行有两个空地,但这两个空地之间没有墙壁,只有草地,所以这两个空地应该属于同一“块”。同样,把竖直方向的块也编上号,如图7.25(b)所示。
把每个横向块看作二部图中顶点集合X 中的顶点,竖向块看作集合Y 中的顶点,若两个块有公共的空地(注意,每两个块最多有一个公共空地),则在它们之间连边。例如,横向块2 和竖向块1 有公共的空地,即(2, 0),于是在X 集合中的顶点2 和Y 集合中的顶点1 之间有一条边。这样,问题转化成一个二部图,如图7.25©所示。由于每条边表示一个空地(即一个横向块和一个竖向块的公共空地),有冲突的空地之间必有公共顶点。例如边(x1, y1)表示空地(0, 0)、边(x2, y1)表示空地(2, 0),在这两个空地上不能同时放置机器人。所以问题转化为在二部图中找没有公共顶点的最大边集,这就是最大匹配问题。
以上面给的样例的构造结果:
#include<bits/stdc++.h>
using namespace std;
int t,n,m,link[2505],ans,num;
int lt,rt;//水平方向上块的个数,垂直方向上块的个数
char c[55][55];//地图
bool flag[2505];
int f1[55][55],f2[55][55];//水平方向上块的编号,垂直方向上块的编号
vector<int> a[2505];
bool find(int x)
{
for(int i=0;i<a[x].size();i++)
if(!flag[a[x][i]])
{
int j=a[x][i];
flag[j]=1;
int q=link[j];
link[j]=x;
if(!q||find(q)) return true;
link[j]=q;
}
return false;
}//最大匹配
int main()
{
cin>>t;
while(t>0)
{
memset(link,0,sizeof(link));
memset(f1,0,sizeof(f1));
memset(f2,0,sizeof(f2));
lt=rt=ans=0;
for(int i=1;i<=2500;i++)
a[i].clear();
t--;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
cin>>c[i][j];
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
if(c[i][j]=='o')
{
lt++;
while(c[i][j]=='o'||c[i][j]=='*')
{
if(c[i][j]=='o')
f1[i][j]=lt;
j++;
}
}
}//求水平方向上块的编号
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
if(c[j][i]=='o')
{
rt++;
while(c[j][i]=='o'||c[j][i]=='*')
{
if(c[j][i]=='o')
f2[j][i]=rt;
j++;
}
}
}//求垂直方向上块的编号
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(c[i][j]=='o')
a[f1[i][j]].push_back(f2[i][j]);//连边
for(int i=1;i<=lt;i++)
{
memset(flag,0,sizeof(flag));
ans+=find(i);
}
num++;
cout<<"Case :"<<num<<endl<<ans<<endl;//格式输出
}
}