1774

• minimum spanning tree
• kruskal's algorithm

---

미리 놓여져 있는 간선 정보가 있고
그 후 각 정점 정보가 입력으로 들어옵니다.

임의의 정점 쌍간의 간선 가중치는 유클리드 거리입니다.

최소 스패닝 트리는 $N - 1$ 개의 간선을 가집니다.
미리 놓인 간선은 $N - 1$ 개의 간선 중 $M$개 입니다.

연결 비용이라는 관점에서 봤을 때
미리 놓인 간선의 연결 비용은 두 정점간의 거리가 아닌 $0$ 입니다.

이를 이용해, 크루스칼 알고리즘으로 간선을 선택하다 보면
선택된 간선의 수는 (미리 놓인 간선을 포함)
$N - 1$ 개가 될 것이며

이후 어떤 임의의 간선도 선택될 수 없습니다.

https://www.acmicpc.net/problem/1774

#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;

vector<pair<int, int>> v;
priority_queue<pair<double, pair<int, int>>> pq;

double ans = 0;
int n, m, p[1001];

int f(int x) {
    return p[x] == x ? x : p[x] = f(p[x]);
}

int u(int a, int b) {
    int x = f(a), y = f(b);
    if (x == y) return 0;
    return p[x] = y;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    v.push_back(make_pair(0, 0));
    
    for (int i = 1; i <= n; i++) {
        p[i] = i;
        int x, y; cin >> x >> y;
        v.push_back(make_pair(x, y));
    }

    for (int i = 1; i <= m; i++) {
        int a, b; cin >> a >> b;
        u(a, b);
    }

    for (int i = 1; i <= n - 1; i++)
        for (int j = i + 1; j <= n; j++) {
            auto p1 = v[i], p2 = v[j];
            pq.push(
                make_pair(
                    -sqrt(pow(p1.first - p2.first, 2) +
                    	  pow(p1.second - p2.second, 2)), 
                    make_pair(i, j)
                )
            );
        }
        
    while (!pq.empty()) {
        auto p = pq.top();
        pq.pop();
        if (u(p.second.first, p.second.second))
            ans += -p.first;
    }

    cout.precision(2); 
    cout << fixed;
    cout << ans << '\n';

    return 0;
}