티스토리 뷰

알고리즘 관련/BOJ

BOJ)4343 Arctic Network

JASON 자손9319 2017. 1. 19. 00:48

문제: icpc.me/4343


P개의 전초기지가 있을 때 S개의 전초기지는 위성채널과 연결되어 있을 때 전초기지 전체가 위성채널과 연결되게 하는데 필요한 마지막 최소 연결비용을 출력하는것이다. 연결비용은 두 전초기지의 거리와 같다.


우리는 P-S개의 간선을 연결하는 MST를 구현하여 마지막으로 연결되는 간선의 가중치를 출력하면 된다.


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
42
43
44
45
46
47
48
49
50
51
52
53
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
int t, n, m, x, y, par[501], c;
pair<intint> p[501];
double r;
double calc(pair<int,int> cx,pair<int,int> cy) {
    return sqrt((cx.first - cy.first)*(cx.first - cy.first) + (cx.second - cy.second)*(cx.second - cy.second));
}
void init() {
    for (int i = 1; i <= n; i++)
        par[i] = i;
}
int find(int x) {
    if (x == par[x])return x;
    return par[x] = find(par[x]);
}
void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y)return;
    c--;
    par[x] = y;
}
int main() {
    scanf("%d"&t);
    while (t--) {
        scanf("%d%d"&m, &n);
        init();
        r = 0.0;
        for (int i = 1; i <= n; i++) {
            scanf("%d%d"&x, &y);
            p[i] = { x,y };
        }
        c = n - m;
        priority_queue<pair<double, pair<intint>>> pq;
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                pq.push({ -calc(p[i],p[j]),{i,j} });
            }
        }
        while (c) {
            r = -pq.top().first;
            x = pq.top().second.first;
            y = pq.top().second.second;
            pq.pop();
            merge(x, y);
        }
        printf("%.2lf\n", r);
    }
    return 0;
}
cs


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

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
BOJ)11974 Subsequences Summing to Sevens  (0) 2017.01.18
댓글
댓글쓰기 폼