Kruskal 10pts 求调
查看原帖
Kruskal 10pts 求调
1137152
SmartCirno楼主2024/10/4 22:19

只过了#1,其它全部是WA

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
#define MAXN 5001
typedef long long ll;
struct Edge
{
	int u,v;
	double w;
	Edge(int u=0,int v=0,double w=999999999999.0):u(u),v(v),w(w){}
	bool operator<(const Edge& other) const
	{
		return w<other.w;
	}
};
struct Vector2
{
	ll x,y;
	Vector2(ll x=0,ll y=0):x(x),y(y){}
	double distance(const Vector2& other)
	{
		double dx,dy;
		dx=x-other.x;
		dy=y-other.y;
		return sqrt(dx*dx+dy*dy);
	}
};
int n,s,f[MAXN];
double ans;
vector<Edge> E;
vector<Vector2> V;
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
void unite(int x,int y){f[find(x)]=find(y);}
void kruskal()
{
	sort(E.begin(),E.end());
	for(const Edge& e:E)
	{
		if(find(e.u)==find(e.v))continue;
		unite(e.u,e.v);
		ans+=e.w;
		s++;
		if(s==n-1)break;
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		ll x,y;
		cin>>x>>y;
		f[i]=i;
		V.push_back(Vector2(x,y));
	}
	for(int i=0;i<n;i++)
	{
		Edge e;
		for(int j=i+1;j<n;j++)
		{
			double dis=V[i].distance(V[j]);
			if(dis<e.w)e=Edge(i,j,dis);
		}
		E.push_back(e);
	}
	kruskal();
	cout<<fixed<<setprecision(2)<<ans;
	return 0;
}

2024/10/4 22:19
加载中...