C++ 代码
/*
思路:
每个牧区选一个点,将两个牧区(连通块)连通,问所有连通后的牧区中直径最小的情况?
连通后的直径:
可能是原来A牧区的直径
可能是原来B牧区的直径
可能是连通A,B牧区的边x(A中一点)->y(B中一点)+A中和x距离最远的距离+B中和y距离最远的距离
三者取最大
最后所有直径取最小
做法:
(1)floyd算法求出任意两点之间的最短距离
(2)预处理maxd[i]-->表示i在自己所在连通块中,距离i最远的点和i之间的距离
max(原来A牧区直径,原来B牧区直径)就是所有maxd[i]的最大值,maxv
连接x(A中点)-y(B中点)后,dist[x,y]+maxd[x]+maxd[y]
res1=max(maxv,dist[x,y]+maxd[d]+maxd[y])-->直径
res=min(res,任意连接x,y得到的res1)
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 155,INF = 1e9;
typedef pair<int, int> PII;
#define x first
#define y second
PII q[N];//存n个点的坐标
char g[N][N];
double dist[N][N];
double maxd[N];
int n;
double get_dist(PII a,PII b)
{
int dx=a.x-b.x;
int dy=a.y-b.y;
return sqrt(dx*dx+dy*dy);
}
int main()
{
cin>>n;
for(int i=0;i<n;i++) cin>>q[i].x>>q[i].y;
for(int i=0;i<n;i++) cin>>g[i];
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(i==j) continue;//dist为0
else if(g[i][j]=='1') dist[i][j]=get_dist(q[i],q[j]);
else dist[i][j]=INF;
}
}
//floyd算法求距离
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
double res1=0;//res1表示在还未将两个牧区相连之前,max(A牧区直径,B牧区直径)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
if(dist[i][j]<INF/2)//如果相连
{
maxd[i]=max(maxd[i],dist[i][j]);
}
res1=max(res1,maxd[i]);
}
double res2=0;//根据情况2和res1存最终直径
double ans=INF;//存答案
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
if(dist[i][j]>INF/2)//如果不相连
{
double distance=get_dist(q[i],q[j])+maxd[i]+maxd[j];
res2=max(distance,res1);//直径
ans=min(ans,res2);
}
}
printf("%.6lf\n",ans);
return 0;
}