模拟的思路,10分求助
查看原帖
模拟的思路,10分求助
577581
00000110hh楼主2022/4/16 17:01
#include<bits/stdc++.h>
using namespace std;
int n;
struct city{
//	long long
	double x,y;
}c[5005];
double mea(int i,int j){
	return (double)(sqrt((double)(c[i].x-c[j].x)*(c[i].x-c[j].x)+(double)(c[i].y-c[j].y)*(c[i].y-c[j].y)));
}
int fa[5005];
struct node{
	int u,v;
	double w=0x7fffffff;
}e[5005];
int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void merge(int x,int y){
	fa[find(fa[x])]=find(fa[y]);
	return;
}
int cnt;
bool cmp(node a,node b){
	return a.w>b.w;
}//最大生成树 
int num;
double ans;
void kruskal(){
	for(int i=1;i<=num;i++){
		int u=e[i].u,v=e[i].v;
		double w=e[i].w;
		if(find(fa[u])!=find(fa[v])){
			merge(fa[u],fa[v]);
			cnt++;
			ans+=w;
			if(cnt==n-1){//记总道路 
				printf("%.2lf  ",ans);
				exit(0);
			}
		}
	}
	return;
}
struct{
	double Min;
	int to;
}flag[5005];//存边之用 
int main(){
	std::ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	for(int i=1;i<=n;i++){
		cin>>c[i].x>>c[i].y;
	}
	while(1){
		for(int i=1;i<=n;i++){
			flag[i].Min=0;
			flag[i].to=0;
		}//初始化 
		num=0;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(find(fa[i])!=find(fa[j])){//不在此城市联盟中 
					if(flag[fa[i]].Min==0||mea(i,j)<flag[fa[i]].Min){
						flag[fa[i]].Min=mea(i,j);//每个城市联盟相连的最短道 
						flag[fa[i]].to=fa[j];
					}
				}
			}
		}
		for(int i=1;i<=n;i++){
			if(flag[i].Min!=0){
				e[++num].u=i;
				e[num].v=flag[i].to;
				e[num].w=flag[i].Min;//存边 
			}
		}
		sort(e+1,e+num+1,cmp);
		kruskal();	
	}
	return 0;
}
2022/4/16 17:01
加载中...