1
struct edge
2
{
3
    int f, t, l;
4
};// 边，是的，我们甚至不需要链式前向星
5
struct cmp
6
{
7
    bool operator()(edge a, edge b)
8
    {
9
        return a.l > b.l;
10
    }
11
};
12

13
std::priority_queue<edge, std::vector<edge>, cmp> pq;// 存储边的优先队列，队顶是最短的边
14

15
std::vector<int>disjoint_set;// 并查集
16
int find(int x)// 查询
17
{
18
    if(disjoint_set[x] != x)
19
        disjoint_set[x] = find(disjoint_set[x]);
20
    return disjoint_set[x];
21
}
22
void init_disjoint_set(int n)// 初始化并查集
23
{
24
    disjoint_set.resize(n);
25
    for(int i = 0; i < n; i++)
26
        disjoint_set[i] = i;
27
}

1
while(!pq.empty())
2
{
3
    // std::clog<<"RUA!"<<std::endl;
4
    edge e = pq.top();// 获取最短边
5
    pq.pop();
6
    int f = find(e.f);
7
    int t = find(e.t);
8
    if(f == t)// 如果这条边属于同一个子最小生成树，那么不进行任何操作
9
        continue;
10
    if(f != t)
11
    {
12
        disjoint_set[f] = t;// 合并子树
13
        cnt += e.l;
14
    }
15
}

1
for(int i = 1; i <= N; i++)
2
{
3
    if(find(i) != find(1))
4
    {
5
        std::cout << "orz" << std::endl;
6
        return 0;
7
    }
8
}
9
std::cout << cnt << std::endl;