菜狗求救,90分
查看原帖
菜狗求救,90分
801941
codingLCX楼主2023/4/5 18:08
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <functional>
#include <vector>
#include <queue>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
using namespace std;
struct edge{
	int a;
	int b;
	double dis;
	edge(int a,int b,double dis):a(a),b(b),dis(dis){};
};
struct cmp{
	bool operator()(edge& a,edge& b){
		return a.dis - b.dis > 0.0000000001;
	}
};
class UnionFindSet{
public:
	vector<int> fa;
	UnionFindSet(int n){
		fa.resize(n);
		iota(fa.begin(),fa.end(),0);
	}
	int find(int a){
		if(fa[a] == a)return a;
		return fa[a] = find(fa[a]); 
	}
	void u(int a,int b){
		int fa_a = find(a);
		int fa_b = find(b);
		fa[fa_a] = fa_b;
	}
	
};
int main(){
	int  n,m;
	cin >> n >> m;//点数和边数
	vector<pair<double,double>> nodes(n + 1);//点的编号从1开始 
	for(int i = 1;i <= n;++i){
		cin >> nodes[i].first >> nodes[i].second;
	}
//	for(int i = 1;i <= n;++i)cout << nodes[i].first << "***" << nodes[i].second << endl;
	//首先创建小根堆并将所有边信息放入堆中 
	priority_queue<edge,vector<edge>,cmp> q;
	for(int i = 1;i <= n;++i){
		for(int j = 1;j <= n;++j){
			if(i == j)continue;
			double difX = nodes[i].first - nodes[j].first;
			double difY = nodes[i].second - nodes[j].second;
			double r = sqrt(difX * difX + difY * difY); 
//			cout << r <<" r" << endl;
			q.push(edge(i,j,r));
		}
	}
	//然后创建并查集 
	UnionFindSet s(n + 1);
	for(int i = 0;i < m;++i){
		int u,v;
		cin >> u >> v;
		if(s.find(u) == s.find(v)){
			--m;
		}else{
			s.u(u,v);
		}
		
	} 
	double ret = 0;
	int cnt = 0;
	while(cnt < n - m  - 1){
		edge e = q.top();q.pop();
		int u = e.a;
		int v = e.b;
		double d = e.dis;
		if(s.find(u) == s.find(v))continue;
		s.u(u,v);
		ret += d;
		++cnt;
	}
	printf("%.2lf",ret);
} 
2023/4/5 18:08
加载中...