分析
先进行一次Kruskal求最小生成树,把最小生成树的边存入ans数组,之后将k-1个边从ans数组中pop出去。最后的答案是ans数组中的最大值。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 510;
int n,k,idx,fa[N];
struct node{
int x,y;
};
struct point{
int a,b;
double w;
bool operator<(const point &p)
{
return w<p.w;
}
}edges[N*N];
vector<double> ans;
int find(int x)
{
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
int main()
{
ios::sync_with_stdio(false);
for(int i=0;i<N;i++) fa[i]=i;
cin>>n>>k;
vector<node> v(n+1);
for(int i=0;i<n;i++)
{
cin>>v[i].x>>v[i].y; //存储点的坐标
}
for(int i=0;i<n;i++) //根据点坐标计算边的长度
{
for(int j=i+1;j<n;j++)
{
double d=sqrt((v[i].x-v[j].x)*(v[i].x-v[j].x)+(v[i].y-v[j].y)*(v[i].y-v[j].y));
edges[idx++]={i,j,d}; //存入edges数组,为后续kruskal算法做准备
}
}
sort(edges,edges+idx);
for(int i=0;i<idx;i++)
{
int a=edges[i].a,b=edges[i].b;
double w=edges[i].w;
int faa=find(a),fbb=find(b);
if(faa!=fbb)
{
fa[faa]=fbb;
ans.push_back(w);
}
}
for(int i=0;i<k-1;i++) ans.pop_back();
double res;
if(ans.empty()) res=0; //如果ans数组空,则不需要花钱,res=0
else res=ans.back();
printf("%.2lf",res);
return 0;
}