学步园

这个题我先开始没有看清楚题意。以为是2到3

结果是要1,2,3相连，那么问题就很明显了。以前做过一个关于跳板的题目

跟这个很相似。

方法就是分别对1,2,3做单源最短路，然后枚举一个跳板i

让dis1[i]+dis2[i]+dis3[i]最小。

然后处理一下就是本题答案了

我的代码：

#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
#define inf 99999999

using namespace std;

struct cir
{
	int x;
	int y;
	int r;
};
struct node
{
	int v;
	int len;
};
vector<node>map[205];
int n;

void spfa(int s,int dis[])
{
	int i,pre[205];
	bool used[205];
	queue<int>q;
	memset(used,0,sizeof(used));
	memset(pre,-1,sizeof(pre));
	for(i=0;i<205;i++)
		dis[i]=inf;
	dis[s]=0;
	used[s]=true;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		used[u]=false;
		for(i=0;i<map[u].size();i++)
		{
			node p=map[u][i];
			if(dis[p.v]>dis[u]+p.len)
			{
				dis[p.v]=dis[u]+p.len;
				pre[p.v]=u;
				if(!used[p.v])
				{
					used[p.v]=true;
					q.push(p.v);
				}
			}
		}
	}
}

void init()
{
	int i;
	for(i=0;i<=n;i++)
		map[i].clear();
}

int max(int a,int b)
{
	if(a>b)
		return a;
	else
		return b;
}

int main()
{
	int t,i,dist1,dist2,j,ans;
	cir c[205];
	node p;
	int dis1[205],dis2[205],dis3[205];
	scanf("%d",&t);
	while(t--)
	{
		init();
		scanf("%d",&n);
		for(i=1;i<=n;i++)
			scanf("%d%d%d",&c[i].x,&c[i].y,&c[i].r);
		for(i=1;i<=n;i++)
		{
			for(j=i+1;j<=n;j++)
			{
				dist1=(c[i].x-c[j].x)*(c[i].x-c[j].x)+(c[i].y-c[j].y)*(c[i].y-c[j].y);
				dist2=(c[i].r+c[j].r)*(c[i].r+c[j].r);
				if(dist1<=dist2)
				{
					p.v=j;
					p.len=1;
					map[i].push_back(p);
					p.v=i;
					map[j].push_back(p);
				}
			}
		}
		spfa(1,dis1);
		spfa(2,dis2);
		spfa(3,dis3);
		ans=-1;
		for(i=1;i<=n;i++)
		{
			if(dis1[i]<inf&&dis2[i]<inf&&dis3[i]<inf)
				ans=max(ans,n-(dis1[i]+dis2[i]+dis3[i]+1));
		}
		printf("%d\n",ans);
	}
	return 0;
}