只有WA,没有其他任何不良反应:)
#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
int n, x, y;
int pa[5010];
double ans;
struct Line{
int x1, y1, x2, y2;
double v;
bool operator<(const Line l) const{ return v<l.v; }
};
double Length(int x1, int y1, int x2, int y2){ return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); }
map<pair<int, int>, int>m;
map<int, pair<int, int> >m2;
int Find(int x){
if(x==pa[x]) return x;
return pa[x]=Find(pa[x]);
}
bool Merge(int a, int b){
int fa=Find(a), fb=Find(b);
if(fa!=fb) pa[fa]=fb;
return fa!=fb;
}
priority_queue<Line>q;
int main(){
cin>>n;
for(int i=1; i<=n; i++){
pa[i]=i;
cin>>x>>y;
m[{x, y}]=i;
m2[i]={x, y};
if(i>1){
int mf=m2[i-1].f, ms=m2[i-1].s;
q.push({mf, ms, x, y, Length(mf, ms, x, y)});
}
}
while(q.size()){
Line l=q.top();
q.pop();
if(Merge(m[{l.x1, l.y1}], m[{l.x2, l.y2}])) ans+=l.v;
}
printf("%.2f", ans);
}
大佬帮忙看看吧。。。