[算法设计与分析] 修复公路 （并查集）

本文主要是介绍[算法设计与分析] 修复公路 （并查集），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

luogu P1111

并查集板子题

然鹅我直接拿kruscal写过了，原因是kruscal同样是把边sort了，选小边

首先把边sort一遍，遍历边，每次加边就进行并查集合并，ans不断更新合并后的最大值，直到所有的点都在里面或者是已经遍历完所有边还是没包括所有点，输出-1

 1 //
 2 //  main.cpp
 3 //  修复公路
 4 //
 5 //  Created by sylvia on 2021/10/31.
 6 //  Copyright © 2021 apple. All rights reserved.
 7 //
 8 //最小生成树模板题 kruscal (x)
 9 //并查集板子
10 #include <iostream>
11 #include <stdio.h>
12 #include <math.h>
13 #include <algorithm>
14 #include <string.h>
15 using namespace std;
16 #define M 1000+5
17 #define N 100000+5
18 struct edge{
19     int u,v,value;
20 }a[N];
21 int cmp(edge x,edge y){
22     return x.value<y.value;
23 }
24 int V,E;  //顶点数与边数
25 int num=0;
26 int father[M],rankk[M];
27 void init(int n){//并查集初始化
28     for (int i=0;i<n;i++){
29         father[i]=i;
30         rankk[i]=0;
31     }
32 }
33 int find(int x){
34     int j,k,r;
35     r=x;
36     while (r!=father[r]) r=father[r];
37     k=x;
38     while (k!=r){
39         j=father[k];
40         father[k]=r;
41         k=j;
42     }
43     return r;
44 }
45 void unite(int x,int y){  //合并集合
46     x=find(x);
47     y=find(y);
48     if(x==y) return;
49     num++;
50     if (rankk[x]<rankk[y]) father[x]=y;
51     else {
52         father[y]=x;
53         if(rankk[x]==rankk[y]) rankk[x]++;
54     }
55 }
56 int same(int x,int y){  //判断是否在一个集合
57     return find(x)==find(y);
58 }
59 
60 int kruskal(){
61     sort(a,a+E,cmp);
62     init(V);
63     int ans=0;
64     for (int i=0;i<E;i++){
65         edge e=a[i];
66         if(!same(e.u,e.v)){
67             unite(e.u,e.v);
68             ans=max(e.value,ans);
69         }
70     }
71     return ans;
72 }
73 int main(){
74     cin>>V>>E;
75     for (int i=0;i<E;i++){
76         cin>>a[i].u>>a[i].v>>a[i].value;
77         
78     }
79     int res= kruskal();
80     if (num==V-1){
81         cout<<res<<endl;
82     }
83     else cout<<-1<<endl;
84     return 0;
85 }

这篇关于[算法设计与分析] 修复公路 （并查集）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！