AcWing1145 北极通讯网络
标签：code col const operator 枚举 ret int hid onclick
这题具有单调性质，可以二分，但是我们发现如果使用并查集维护kruscal，那么无需二分，直接枚举答案即可
#include#define x first
#define y second
using namespace std;
typedef pairint,int> pll;
const int N=510000;
struct node{
int a,b;
double c;
bool operator const node &t) const{
return ct.c;
}
}e[N];
pll q[N];
int p[N];
double get(pll a,pll b){
int x=a.x-b.x;
int y=a.y-b.y;
return sqrt(x*x+y*y);
}
int find(int x){
if(x!=p[x]){
p[x]=find(p[x]);
}
return p[x];
}
int main(){
int n,k;
int i,j;
cin>>n>>k;
for(i=1;i){
cin>>q[i].x>>q[i].y;
}
for(i=1;i)
p[i]=i;
int cnt=0;
for(i=1;i){
for(j=1;j){
e[cnt++]=node{i,j,get(q[i],q[j])};
}
}
sort(e,e+cnt);
double res=0;
int tmp=n;
for(i=0;i){
if(tmpk)
break;
int pa=find(e[i].a),pb=find(e[i].b);
if(pa!=pb){
p[pa]=pb;
tmp--;
res=e[i].c;
}
}
printf("%.2f\n",res);
}
View Code
AcWing1145 北极通讯网络
标签：code col const operator 枚举 ret int hid onclick
原文地址：https://www.cnblogs.com/ctyakwf/p/12838290.html
评论