题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=3832
题意:有n块区域,求保证前三个区域联通的情况下最多可以删掉几个区域;
可以想象最优连通方案不是一条链就是一个三叉。因为是无权的,最少点数实际上就是最短路。当分叉点在特定点上的时候,三叉就退化为一条链,所以我们只需要枚举分叉点即可。
先3次bfs求出各个点到0,1,2三个区域的最短路,然后枚举点求联通最小量
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
using namespace std;
#define eps 1e-6
#define INF 1000000
struct Point
{
double x,y,r;
}p[230];
int n,d[3][230],map[230][230];
int vis[230];
double dis(Point a,Point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void init()
{
scanf("%d",&n);
memset(map,0,sizeof(map));
for(int i=0;i<3;i++)
for(int j=0;j<n;j++)
d[i][j]=INF;
d[0][0]=0;
d[1][1]=0;
d[2][2]=0;
for(int i=0;i<n;i++)
{
scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].r);
}
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
{
if(dis(p[i],p[j])-p[i].r-p[j].r<=eps)
{
map[i][j]=1;
map[j][i]=1; // 在有公共区域的圆之间建边
}
}
}
void bfs(int k)
{
memset(vis,0,sizeof(vis));
queue<int> q;
q.push(k);
vis[k]=1;
d[k][k]=0;
while(!q.empty())
{
int x=q.front();q.pop();
for(int i=0;i<n;i++)
if(!vis[i]&&map[x][i])
{
vis[i]=1;
d[k][i]=d[k][x]+1;
q.push(i);
}
}
}
int main()
{
int Case;
scanf("%d",&Case);
while(Case--)
{
init();
int ans=INF;
bfs(0);
bfs(1);
bfs(2);
for(int i=0;i<n;i++) //枚举分叉点(也包括链的情况)
{
if(d[1][i]+d[2][i]+d[0][i]+1<ans)
ans=d[1][i]+d[2][i]+d[0][i]+1;
}
if(ans==INF)printf("-1\n");
else printf("%d\n",n-ans);
}
return 0;
}