洛谷 P1547 Out of Hay （最小生成树）

嗯...

题目链接：https://www.luogu.org/problemnew/show/P1547

思路：

嗯...既然题中已经说了是最小生成树，那么是需要在最小生成树的模板上稍作修改即可。要求的是最小生成树中的最长边，注意：

一. 不是每一条边都可以做为最小生成树中的边。

二. 所要求的这条边是连接两个点的边的最大权值。

所以，我们就在“并”操作的时候稍作修改，用ans记录下它的最大权值即可。

AC代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 
 5 using namespace std;
 6 
 7 int f[100005];
 8 int ans;
 9 
10 struct node{
11     int x, y, l;
12 } a[1000005];
13 
14 inline int cmp(node i, node j){
15     return i.l < j.l;
16 }
17 
18 inline int find(int x){
19     if(f[x] != x)
20         f[x] = find(f[x]);
21     return f[x];
22 }//"查" 
23 
24 int main(){
25     int n, m;
26     scanf("%d%d", &n, &m);
27     for(int i = 1; i <= m; i++){
28         scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].l);
29     }
30     for(int i = 1; i <= n; i++)
31         f[i] = i;
32     sort(a+1, a+1+m, cmp);//按边权排序，"最小" 
33     for(int i = 1; i <= m; i++){
34         int r1 = find(a[i].x);
35         int r2 = find(a[i].y);
36         if(r1 != r2){
37             f[r1] = r2;
38             ans = max(ans, a[i].l);//维护最大边权 
39         }//"并" 
40     }
41     printf("%d", ans);
42     return 0;
43 }

AC代码

洛谷 P1547 Out of Hay （最小生成树）

相关推荐