大型网站建设公司制作网站,淄博做网站建设的公司,能看小视频的浏览器,wordpress cos插件正题
评测记录:https://www.luogu.org/recordnew/lists?uid52918pidP1522 题目大意
有n个点#xff0c;连接任意两个不同联通块上的点#xff0c;使这个新的联通块之间最远的两个点的距离最远。 解题思路
先FlodyO(n3)O(n^3)O(n3)计算两两之间的距离 然后计算出每个…正题
评测记录:https://www.luogu.org/recordnew/lists?uid52918pidP1522 题目大意
有n个点连接任意两个不同联通块上的点使这个新的联通块之间最远的两个点的距离最远。 解题思路
先FlodyO(n3)O(n^3)O(n3)计算两两之间的距离 然后计算出每个点最远的点的距离之后对于枚举两个不同联通块中的点那么可能产生的新的权值就是两个个点的最远的点距离加上这两个点之间的距离但是还要和合并前联通块中最远的点的距离比较 code
// luogu-judger-enable-o2
#includecstdio
#includealgorithm
#includecmath
#includeiostream
#define N 160
#define pows(x) x*x
using namespace std;
int n,inx[N],tot;
double x[N],y[N],a[N][N],d[N],md[N],mins;
char c;
double const_dis(int i,int j)
{return sqrt((x[i]-x[j])*(x[i]-x[j])(y[i]-y[j])*(y[i]-y[j]));
}
void dfs(int x)//分联通块
{inx[x]tot;for(int i1;in;i)if(!inx[i]a[x][i]!2147483647)dfs(i);
}
int main()
{scanf(%d,n);for(int i1;in;i)scanf(%lf%lf,x[i],y[i]);for(int i1;in;i)for(int j1;jn;j){cinc;if(c1)a[i][j]const_dis(i,j);else if(i!j) a[i][j]2147483647;}for(int i1;in;i)if(!inx[i]) tot,dfs(i);for(int k1;kn;k)for(int i1;in;i)for(int j1;jn;j)if(a[i][k]a[k][j]a[i][j])a[i][j]a[i][k]a[k][j];//计算最短路for(int i1;in;i){for(int j1;jn;j)if(a[i][j]!2147483647)md[i]max(md[i],a[i][j]);//每个点的最远距离d[inx[i]]max(d[inx[i]],md[i]);//每个联通块最远距离}mins2147483647;for(int i1;in;i)for(int ji1;jn;j)if(inx[i]!inx[j])minsmin(mins,max(md[i]md[j]const_dis(i,j),max(d[inx[i]],d[inx[j]])));printf(%.6lf,mins);
}
