문제 풀이

최소 스패닝 트리를 구성하는 문제, 먼저 Edge라는 구조체를 만들어 간선의 양 정점과 거리를 저장할 수 있도록한다
우선 순위큐를 사용하고 정점간의 거리를 기준으로 오름차순으로 정렬할것이기 때문에 cmp함수를 작성해준다.
크루스칼 알고리즘을 사용할 것이기 때문에 유니온파인드를 사용한다.
크루스칼 알고리즘은 간선의 비용이 낮은순부터 하나하나 최소 스패닝 트리에 추가하는 방식이고, 최소 스패닝 트리는 사이클이 존재하지 않아야 하기 때문에 유니온 파인드를 활용해준다.

이제, 정점들의 위치를 입력받아주고 이중 for문을 통해서 정점간의 각 거리를 구해주고 우선순위큐에 push 해준다.
그리고 m개의 이미 연결된 정보를 받고 각 정점을 미리 Union 시켜준다.

최소 스패닝트리에서 간선의 수는 n-1개이다.

• 비용이 낮은순으로(우선순위 큐의 top부터)
• 사이클이 발생하지 않도록(부모가 다름)
  트리에 추가를 할 것인데 추가할 때마다 각 정점을 Union 해주고 Union되었다면 앞으로 추가해야되는 횟수를 뜻하는 edges를 하나 빼준다.

문제 링크

boj/1774

소스코드

PS/1774.cpp

#include<vector>
#include<algorithm>
#include<math.h>
#include<queue>
using namespace std;
int p[1001];
vector<pair<int, int>> v;
struct Edge
{
	int v1, v2;
	double dis;
};
struct cmp
{
	bool operator()(const Edge& s1, const Edge& s2) {
		return s1.dis > s2.dis;
	}
};
int getParent(int x)
{
	if (p[x] == x)
		return x;
	return x = getParent(p[x]);
}

void Union(int a, int b)
{
	a = getParent(a);
	b = getParent(b);
	if (a == b)
		return;
	if (a < b)
		p[b] = a;
	else
		p[a] = b;
}
priority_queue<Edge, vector<Edge>, cmp> pq;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++)

	{
		p[i] = i;
		int x, y;
		cin >> x >> y;
		v.push_back({ x,y });
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (i == j)
				continue;
			Edge e;
			e.v1 = i + 1;
			e.v2 = j + 1;
			e.dis = sqrt(pow(v[i].first - v[j].first, 2) + pow(v[i].second - v[j].second, 2));
			pq.push(e);
		}
	}
	int edges = n - 1;
	for (int j = 0; j < m; j++)
	{
		int a, b;
		cin >> a >> b;
		if (getParent(a) != getParent(b))
		{
			Union(a, b);
			edges--;
		}
	}
	long double ans = 0;

	while (edges)
	{
		Edge e = pq.top();
		if (getParent(e.v1) != getParent(e.v2))
		{
			edges--;
			Union(e.v1, e.v2);
			ans += e.dis;
		}
		pq.pop();
	}
	cout.precision(2);
	cout << fixed;
	cout << ans;
}