//北极通讯网络 
//#include<bits/stdc++.h>
#include<cmath>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
struct Node{
	int b,e;
	double w;
	bool operator <(const Node &a) const{
		return w<a.w;
	}
};
struct OP{
	int x,y;
}op[510];
int N,S,P,fa[510];
double ans=0;
int Find(int x){
	if(fa[x]==x) return x;
	return fa[x]=Find(fa[x]);
}
void Join(int x,int y){
	fa[Find(x)]=Find(y);
}
vector<Node > edge;
int main(){
	cin>>N;
	for(int i=0;i<N;i++){
		cin>>S>>P;
		for(int j=1;j<=P;j++){
			cin>>op[j].x>>op[j].y;
			fa[j]=j;
			for(int k=1;k<j;k++){
				Node tmp;
				tmp.b=j,tmp.e=k,tmp.w=sqrt(double((op[j].x-op[k].x)*(op[j].x-op[k].x)+(op[j].y-op[k].y)*(op[j].y-op[k].y)));
				edge.push_back(tmp);
			}
		}
		sort(edge.begin(),edge.end());
		int cnt=0;
		for(int j=0;j<edge.size();j++){
			//cout<<edge[j].b<<" "<<edge[j].e<<" "<<edge[j].w<<endl;
			if(Find(edge[j].b)!=Find(edge[j].e)){
				Join(edge[j].b,edge[j].e);
				cnt++;
				ans=edge[j].w;
			}
			if(cnt==P-S) break;
		}
		printf("%.2lf\n",ans);
	}
	return 0;
}

• Re:为什么WA了 (1232) likeWater 2022-03-26 09:59:59