티스토리 뷰

알고리즘 관련/BOJ

BOJ)1647 도시 분할 계획

JASON 자손9319 2017. 1. 6. 14:12

문제: icpc.me/1647


최소 스패닝 트리를 구해주면 된다.


주의할 점은 하나인 마을을 두개로 나누고 싶다고 하고 있기 때문에 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
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
vector<pair<int, pair<intint>>> vt;
int n, m, a, b, c, r;
int par[100010];
int find(int x) {
    if (par[x] == x)return x;
    return par[x] = find(par[x]);
}
void merge(int x, int y,int z) {
    x = find(x);
    y = find(y);
    if (x == y)return;
    par[x] = y;
    r += z;
    n--;
}
int main() {
    freopen("input.txt""r", stdin);
    scanf("%d%d"&n, &m);
    for (int i = 1; i <= n; i++)
        par[i] = i;
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d"&a, &b, &c);
        vt.push_back({ c,{a,b} });
    }
    sort(vt.begin(), vt.end());
    for (auto it : vt) {
        if (n == 2)break;
        int x = it.second.first;
        int y = it.second.second;
        int z = it.first;
        merge(x, y, z);
    }
    printf("%d\n", r);
    return 0;
}
cs


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

BOJ)4627 뛰어라 도마뱀  (0) 2017.01.06
BOJ)13701 중복 제거  (0) 2017.01.06
BOJ)1647 도시 분할 계획  (0) 2017.01.06
BOJ)4948 베르트랑 공준  (0) 2017.01.06
BOJ)12842 튀김 소보루  (0) 2017.01.05
BOJ)13505 두수 XOR  (4) 2017.01.05
댓글
댓글쓰기 폼