P2872

用了 kruskal 求最小生成树

#include<iostream>
#include<cmath>
#include<algorithm>
#include<iomanip>
using namespace std;

const int MAXN = 1005, MAXM = 1005;

struct Edge
{
	int u, v;
	double w;
	bool p = false;
};
int n, m, cnt = 0;
double ans = 0;
Edge edge[MAXM*MAXM];
int fa[MAXN];
double x[MAXN], y[MAXN];
bool vis[MAXN][MAXM];

double dis(double x1, double y1, double x2, double y2)
{
	double result;
	result = double(sqrt(double((x1-x2) * (x1-x2)) + double((y1-y2) * (y1-y2))));
	return result;
}

int find(int x)
{
	while(x != fa[x])
	{
		x = fa[x];
	}
	return x;
}

void join(int x, int y)
{
	fa[y] = x;
}

void init()
{
	for(int i = 1; i <= n; i++)
	{
		fa[i] = i;
	}
}

bool cmp(Edge a, Edge b)
{
	return a.w < b.w;
}

void solve()
{
	for(int i = 1; i <= m; i++)
	{
		cin >> edge[i].u >> edge[i].v;
		edge[i].w = dis(x[edge[i].u], y[edge[i].u], x[edge[i].v], y[edge[i].v]);
		vis[edge[i].u][edge[i].v] = 1;
		vis[edge[i].v][edge[i].u] = 1;
		join(edge[i].u, edge[i].v);
		cnt++;
	}
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			if(vis[i][j] == 0)
			{
				vis[i][j] = 1;
				vis[j][i] = 1;
				m++;
				edge[m].u = i, edge[m].v = j, edge[m].w = dis(x[i], y[i], x[j], y[j]);
			}
		}
	}
	sort(edge+1, edge+1+m, cmp);
	for(int i = 1; i <= m; i++)
	{
		if(find(edge[i].u) != find(edge[i].v))
		{
			join(edge[i].u, edge[i].v);
			ans += edge[i].w;
			cnt++;
		}
		if(cnt == n-1)
		{
			break;
		}
	}
}

int main()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
	{
		cin >> x[i] >> y[i];
	}
	init();
	solve();
	cout << fixed << setprecision(2) << ans << endl;
	return 0;
}