P3366

Posted on In , Views:

題目:
https://www.luogu.com.cn/problem/P3366

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
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
#define MAXN 5005
using namespace std;

struct Edge{
    int x, y;
    int len;
    bool operator<(const Edge& o) const{
        return len < o.len;
    }
};

int f[MAXN];
int len[MAXN];
vector<Edge> v;

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

bool isSameSet(int x, int y){
    return (find(x) == find(y));
}

void Union(int x, int y){
    int f_x = f[x];
    int f_y = f[y];
    if(find(f_x) != find(f_y)){
        f[f_y] = f_x;
    }
}

int main(){
    int n, m; // n nodes, m edges
    cin >> n >> m;
    bool found = true;
    for(int i=1; i<=n; ++i){
        f[i] = i;
        len[i] = 0;
    }
    int x, y, z; // x to y with len z
    for(int i=1; i<=m; ++i){
        cin >> x >> y >> z;
        v.push_back({x, y, z});
    }
    sort(v.begin(), v.end());
    int total = 0;
    for(Edge e : v){
        if(!isSameSet(e.x, e.y)){
            total += e.len;
            Union(e.x, e.y);
        }
    }
    for(int i=2; i<=n; ++i){
        if(find(1) != find(i)){
            found = false;
            break;
        }
    }
    if(!found) cout << "orz\n";
    else cout << total << '\n';
    return 0;
}