kruskal 20分 8个点wrong
查看原帖
kruskal 20分 8个点wrong
302750
Main_WF楼主2021/7/15 19:05
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;

struct node{
	int u,v;
	double w;
	bool operator <(const node &t)const{
		return w<t.w;
	}
}e[maxn];
int k=0;

int n,m;
int f[maxn];
long long x[maxn];
long long y[maxn];

double dal(long long x1,long long x2,long long y1,long long y2)
{
	return sqrt(pow(x1-x2,2)+pow(y1-y2,2));
}

void add(int u,int v,double w)
{
	k++;
	e[k].u=u;e[k].v=v;e[k].w=w;
}

int find(int v)
{
	if(v!=f[v])f[v]=find(f[v]);
	return f[v];
}

void hb(int a,int b)
{
	int fa=find(a);
	int fb=find(b);
	f[fa]=fb;
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)//读入点坐标 
		cin>>x[i]>>y[i];
	
	for(int i=1;i<=n;i++)//每个点都建一条边 
		for(int j=i+1;j<=n;j++)
			add(i,j,dal(x[i],x[j],y[i],y[j]));	
	
	for(int i=1;i<=m;i++)//必入的边 
	{
		int u,v;
		cin>>u>>v;
		add(u,v,0.0);
	}
	
	for(int i=1;i<=n;i++)f[i]=i;//并查集初始化 
	sort(e+1,e+1+k);//边排序
	
	int v=n; 
	double ans=0;
	int i=1;
	while(v>1)
	{
		if(i==k+1)break;
		if(find(e[i].u)!=find(e[i].v))
		{
			ans+=e[i].w;
			hb(e[i].u,e[i].v);
			v--;
		}
		i++;
	}
	printf("%.2f",ans);
}
2021/7/15 19:05
加载中...