标签：最小生成树，并查集
题目
分析
加边之前判断下是否合法即可
之后常规模板题
Code
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define mem(x,num) memset(x,num,sizeof x)
#define ll long long
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
//******head by yjjr******
const int maxn=106;
struct edge{int u,v;double w;}e[maxn*maxn];
struct node{int x,y;}a[maxn];
int n,tot,cnt,num,fa[maxn],T;double ans;
inline bool cmp(edge a,edge b){return a.w<b.w;}
inline int find(int x){return x==fa[x]?fa[x]:fa[x]=find(fa[x]);}
inline double dis(int s,int t){return sqrt((a[s].x-a[t].x)*(a[s].x-a[t].x)+(a[s].y-a[t].y)*(a[s].y-a[t].y));}
void kruskal(){
sort(e+1,e+1+cnt,cmp);
rep(i,1,cnt){
int r1=find(e[i].u),r2=find(e[i].v);
if(r1!=r2){ans+=e[i].w;fa[r1]=r2;tot++;}
}
}
int main(){
T=read();
while(T--){
n=read();
rep(i,1,n)scanf("%d%d",&a[i].x,&a[i].y);
rep(i,0,n+1)fa[i]=i;
cnt=0,tot=0;ans=0.0;
rep(i,1,n-1)
rep(j,i+1,n)
if(dis(i,j)>=10.0&&dis(i,j)<=1000.0)e[++cnt]=(edge){i,j,dis(i,j)};
kruskal();
if(tot==n-1)printf("%.1lf\n",ans*100);else puts("oh!");
}
return 0;
}
