求调,Kruskal WA 10pts
查看原帖
求调,Kruskal WA 10pts
1104948
cc_lucky楼主2024/7/10 21:11

只有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);
}

大佬帮忙看看吧。。。

2024/7/10 21:11
加载中...