Floyd
题意
给你一个n*n的邻接矩阵,得到连通牧场。问如果连接任意两个不相连的牧场,求出一个最短的直径。
解法
给的是坐标,所以必须会两点之间距离公式.sqrt((x2-x1)(x2-x1)+(y2-y1)(y2-y1));
然后Floyd跑出两点之间距离,求出每个点能到的最远的牧场距离,然后枚举任意两个不相连的点,求最短直径。
参考代码
#include<bits/stdc++.h>
using namespace std;
#define N 1005
#define INF 0x3f3f3f3f
int x[N*N],y[N*N];
int n;
char s[N*N];
double cd[N*N];
double len[N][N];
double maxx;
double calc(int x1,int y1,int x2,int y2) {
return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}
int main() {
memset(len,127,sizeof(len));
scanf("%d",&n);
for(int i=1; i<=n; i++) {
scanf("%d %d",&x[i],&y[i]);
}
for(int i=1; i<=n; i++) {
scanf("%s",s+1);
for(int j=1; j<=n; j++) {
if(i!=j) {
if(s[j]=='0') {
len[i][j]=INF;
len[j][i]=INF;
} else {
len[i][j]=calc(x[i],y[i],x[j],y[j]);
len[j][i]=len[i][j];
}
} else
len[i][j]=0;
}
}
for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++) {
if(len[i][j]>len[i][k]+len[k][j])
len[i][j]=min(len[i][j],len[i][k]+len[k][j]);
}
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
if(len[i][j]<INF&&len[i][j]>cd[i])
cd[i]=len[i][j];
maxx=INF;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++) {
if(len[i][j]==INF&&maxx>cd[i]+cd[j]+calc(x[i],y[i],x[j],y[j])) {
maxx=cd[i]+cd[j]+calc(x[i],y[i],x[j],y[j]);
}
}
for(int i=1; i<=n; i++)
maxx=max(maxx,cd[i]);
printf("%.6f",maxx);
}