并查集知识点回顾(最小生成树)

题目链接: https://www.luogu.org/problem/P1111

思路: 先以时间排序,然后一条一条连接,直到连接了n-1条边,即可输出最小时间,否则输出-1;n个点要使得任意一个点与另一个相连,那最少需要n-1条边!

代码

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
#include <bits/stdc++.h>
using namespace std;
int vis[100005];
struct node{
int x;
int y;
int v;
};
int findx(int x)
{
int r = x;
while(r != vis[r])
r = vis[r];
int k = x, tmp;
while(k != r){
tmp = vis[k];
vis[k] = r;
k = tmp;
}

return r;
}
int marge(int a, int b){
int x = findx(a);
int y = findx(b);
if(x != y){
vis[y] = x;
return -1;
}
return 0;
}
int cmp(node a, node b){
return a.v < b.v;
}
int main()
{
ios::sync_with_stdio(false);
int n, m;
while(cin >> n >> m){
vector<node> ve;
for(int i = 1; i <= n; i++) vis[i] = i;
for(int i = 1; i <= m; i++){
int a, b, c;
cin >> a >> b >> c;
ve.push_back(node{a, b, c});
}
sort(ve.begin(), ve.end(), cmp);
for(int i = 0; i < m; i++){
n += marge(ve[i].x, ve[i].y);
//cout << n << endl;
if(n == 1){
cout << ve[i].v << endl;
break;
}
}
if(n != 1){
cout << -1 << endl;
}
}
return 0;
}

本文标题:并查集知识点回顾(最小生成树)

文章作者:HKer_YM

发布时间:2019年10月04日 - 15:20:14

最后更新:2020年03月01日 - 12:30:17

原始链接:https://blog.dreams-wj.top/2019/10/04/%E5%B9%B6%E6%9F%A5%E9%9B%86%E7%9F%A5%E8%AF%86%E7%82%B9%E5%9B%9E%E9%A1%BE-%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。