求问一道最小生成树模板题
查看原帖
求问一道最小生成树模板题
324573
Sin_qwq楼主2021/11/3 07:38
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
const int N=500100;
int n,m;
int tot=0,num=0;
double sum=0.00;
int fa[N];
struct E{
	int nxt,to;
	double vl;
}e[N];
struct node{
	int x,y;
}a[N];
bool cmp(E a,E b)
{
	return a.vl<b.vl;
}
inline void add_edge(int u,int v,double w)
{
	tot++;
	e[tot].nxt=u;
	e[tot].to=v;
	e[tot].vl=w;
}
inline int find(int x)
{
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
inline double dist(int x1,int y1,int x2,int y2)
{
	return (double)sqrt((double)(x1-x2)*(x1-x2)+(double)(y1-y2)*(y1-y2));
}
inline void kru()
{
	for(int i=1;i<=tot;i++)
	{
		int x=find(e[i].nxt);
		int y=find(e[i].to);
		if(x==y) continue;
		fa[x]=y;
		sum+=e[i].vl;
		if(++num==n-1) printf("%.2lf\n",sum);
	}
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
    for(int i=1;i<=m;i++)
    {
    	int u,v;
    	cin>>u>>v; 
    	double w=dist(a[u].x,a[u].y,a[v].x,a[v].y);
    	add_edge(u,v,w);
    	add_edge(v,u,w);
	}
	sort(e+1,e+tot+1,cmp);
	kru();
	return 0;
}


怎么会无法输出呢?

2021/11/3 07:38
加载中...