#include<bits/stdc++.h>
#define db double
using namespace std;
const int maxn=1014514;
const int maxx=1145;
int cnt=0;db ans=0.0;
struct edge{
db u,v,w;
}a[maxn];
struct node{
int x,y;
}aa[maxx];
db fa[maxx];
int n,m;
bool compare(edge a,edge b){
return a.w<b.w;
}
int find(int x){
if(fa[x]==x)return x;
else return fa[x]=find(fa[x]);
}
void kruskal(){
int now=0;
sort(a+1,a+cnt+1,compare);
for(int i=1;i<=cnt;i++){
now++;
if(find(a[now].u)!=find(a[now].v)){
ans+=a[now].w;
fa[find(a[now].u)]=find(a[now].v);
}
// if(now>=n)break;
}
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>aa[i].x>>aa[i].y;
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){
a[++cnt].u=i;
a[cnt].v=j;
a[cnt].w=(db)sqrt((db)(aa[i].x-aa[j].x)*(aa[i].x-aa[j].x)+(db)(aa[i].y-aa[j].y)*(aa[i].y-aa[j].y));
}
for(int i=1;i<=m;i++){
int aaa,bbb;
cin>>aaa>>bbb;
a[++cnt].u=aaa;
a[cnt].v=bbb;
a[cnt].w=0.0;
}
kruskal();
cout<<fixed<<setprecision(2)<<ans<<endl;
return 0;
}
上面是AC代码,前几次我交只过了10分,唯一的区别在于我之前的加了这句话
if(now>=n)break; //AC程序中这句话是注释掉的
我记得最小生成树板子就得加上这句话(因为已经连了所有的边)但是为什么这道题不行呢