티스토리 뷰

알고리즘 관련/BOJ

BOJ)4386 Freckles

JASON 자손9319 2017. 1. 19. 01:15

문제: icpc.me/4386


N개의 점들이 주어지고 각 점들사이의 가중치는 거리와 비례한다 할 때 MST를 구성하는 문제다.


N이 100밖에 되지 않으니 N^2의 방법으로 간선들을 구해준 후 크루스칼을 돌려주면 된다.


 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
int n, par[101], it;
double r;
pair<doubledouble> p[101];
priority_queue<pair<double, pair<intint>>> pq;
double calc(pair<doubledouble> cx, pair<doubledouble> cy) {
    return sqrt((cx.first - cy.first)*(cx.first - cy.first) + (cx.second - cy.second)*(cx.second - cy.second));
}
int find(int x) {
    if (par[x] == x)return x;
    return par[x] = find(par[x]);
}
void merge(int x, int y, double c) {
    x = find(x);
    y = find(y);
    if (x == y)return;
    it--;
    par[x] = y;
    r += c;
}
int main() {
    scanf("%d"&n);
    for (int i = 1; i <= n; i++
        scanf("%lf%lf"&p[i].first, &p[i].second);
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++)
            pq.push({ -calc(p[i],p[j]),{i,j} });
    }
    for (int i = 1; i <= n; i++)
        par[i] = i;
    it = n - 1;
    while (it) {
        merge(pq.top().second.first, pq.top().second.second, -pq.top().first);
        pq.pop();
    }
    printf("%.2lf\n", r);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)2623 음악프로그램  (3) 2017.01.20
BOJ)11438 LCA 2  (0) 2017.01.19
BOJ)4386 Freckles  (0) 2017.01.19
BOJ)4343 Arctic Network  (0) 2017.01.19
BOJ)13325 이진 트리  (1) 2017.01.18
BOJ)11975 Build Gates  (0) 2017.01.18
댓글
댓글쓰기 폼