Prim & Kruskal

最小生成树两个板子&习题

  • 最小生成树的$prim$算法和$kruskal$算法的个人理解，记录一下。

最小生成树

概念

  • 最小生成树是一副连通加权无向图中一颗权值最小的生成树

$Prim$算法

原理

  • 与$Dijkstra$算法相类似，对于图中的任意一个节点，找出与之相连的权值最小的边，并连接上去，同时更新答案，并将该点标记为已用过，当找到的边数==点数-1时结束

注意事项：

  1. 存图（链式前向星）时必须存双向边，因此边数组需要开两倍大
  2. dis数组是核心，它表示已用点到未用点的最短距离

代码

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=5005;
const int maxm=200005;
const int inf=1<<30;
struct Edge{ //边结构体
	int u,v,w,next;
}e[2*maxm];
int n,m,cnt,tot,head[maxn],ans,now=1,vis[maxn],dis[maxn];
inline void addedge(int u,int v,int w){ //加边函数
	e[++cnt].u=u;
    e[cnt].v=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt;
}

inline void prim(){ //算法主体
    //先把除了1点之外的点置为无穷
	for(int i=2;i<=n;i++) dis[i]=inf; 
    //遍历与第一个点相连的边，注意防重边
    for(int i=head[1];i;i=e[i].next){ 
		dis[e[i].v] = min(dis[e[i].v],e[i].w);
    }
    //最小生成树边数=点数-1
    while(++tot<n){
		int minh=inf; //每次找到的边的最小值
        vis[now]=1; //一定要标记，排除环的出现
        //一定是遍历所有的点，因为任何时候都有可能出现 别的点相连的边权值更小
        for(int i=1;i<=n;i++){
			if(!vis[i]&&dis[i]<minh){
				minh=dis[i]; // 更新最小值
                now=i; //同时更新当前点
            }
        }
        ans+=minh; //更新答案
        //更新与当前点相连的所有边的权值（一定要更新，否则就还是无穷）
        for(int i=head[now];i;i=e[i].next){
            int v=e[i].v;
            if(!vis[v]&&dis[v]>e[i].w){
                dis[v]=e[i].w;
            }
        }
    }
}

int main(){
	cin>>n>>m;
    for(int i=1;i<=m;i++){
		int u,v,w;
        cin>>u>>v>>w;
        //一定加双向边，因为要遍历所有点的情况
        addedge(u,v,w); 
        addedge(v,u,w);
    }
    prim();
    cout<<ans<<endl;
    return 0;
}

$Kruskal$算法

原理

  • 与$prim$算法不同，$kruskal$算法首先对所有边权排序，然后从小到大遍历每一条边，每次将权值最小的边加入答案并连接其两个节点（采用并査集完成连接操作，避免了环的产生），从而找到最小生成树

注意事项：

  1. 存图（链式前向星）时无需存双向边和next，因为算法开始时需要先进行排序操作

代码

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=5005;
const int maxm=200005;
const int inf=1<<30;

struct Edge{
	int u,v,w;
}e[maxm];

bool cmp(Edge x1,Edge x2){
    return x1.w<x2.w;
}

int n,m,fa[maxn],ans,cnt;
inline void addedge(int u,int v,int w){
    e[++cnt].u=u;
    e[cnt].v=v;
    e[cnt].w=w;
}

// 以下是并査集模板（路径压缩）
inline int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}

inline void unite(int x,int y){
    fa[find(x)]=find(y);
}
// 初始化非常重要
inline void init(int n){
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
}

inline void kruskal(){ //算法主体
    sort(e+1,e+1+m,cmp); //对边结构体按边权排序
    for(int i=1;i<=m;i++){ //从小到大遍历边
    	int eu=e[i].u,ev=e[i].v;
        if(find(eu)==find(ev)) continue; //如果在同一个树里就continue
        ans+=e[i].w; //更新答案
        unite(eu,ev); //把节点连起来
    }
}

int main(){
    cin>>n>>m;
    init(n);
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
       	addedge(u,v,w);
    }
    kruskal();
    cout<<ans<<endl;
    return 0;
}
  • 可以看出$kruskal$算法的代码量相比$prim$算法来说特别友好，这还是要归功于并査集代码的简洁性，堪称神器。

习题

1. Vijos P1190 繁忙的都市

题意

  • 翻译过来就是：给你一个无向带权图，问你选了几条边，其中边权最大的权值是多少？

题解

  • 裸的$kruskal$，直接写就好。

AC代码

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
#include<bits/stdc++.h>
using namespace std;
struct Edge{
    int u,v,w;
}e[3000005];

bool cmp(Edge x1,Edge x2){
    return x1.w<x2.w;
}

int n,m,fa[1000005],ans,anss,cnt;

inline void addedge(int u,int v,int w){
    e[++cnt].u=u;
    e[cnt].v=v;
    e[cnt].w=w;
}

inline void init(int n){
    for(int i=1;i<=n;i++) fa[i]=i;
}

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

inline void unite(int x,int y){
    fa[find(x)]=find(y);
}

inline void kruskal(){
    sort(e+1,e+1+m,cmp);
    for(int i=1;i<=m;i++){
        int eu=e[i].u,ev=e[i].v;
        if(find(eu)==find(ev)) continue;
        anss=max(anss,e[i].w);
        ans++;
        unite(eu,ev);
    }
}

int main(){
    cin>>n>>m;
    init(n);
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        addedge(u,v,w);
    }
    kruskal();
    cout<<ans<<" "<<anss;
    return 0;
}

2. Vijos P1234 口袋的天空

题意

  • 给你很多个节点和一些边，连接一条边需要付出边权的代价，问能否组成k个不连通的图，若可以，求出最小的代价，若不可以，输出“No Answer”。

题解

  • 我的思路：也是裸的$kruskal$，在算法过程中将每次加入的边权存入一个顺序数组中，$kruskal$结束后遍历一遍节点，找到全部连边情况下剩下几个不连通的图（也就是所能产生的最少的图）设为n，如过k<n，则不可能，否则就从边权数组里倒序遍历n-k个权值，并用最小生成树减去这个数值即可。

AC代码

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
64
65
66
67
68
69
70
71
72
#include<bits/stdc++.h>
using namespace std;
struct Edge{
    int u,v,w,next;
}e[3000005];

bool cmp(Edge x1,Edge x2){
    return x1.w<x2.w;
}

int n,m,k,fa[1000005],ans,anss,cnt,head[1000005];

inline void addedge(int u,int v,int w){
    e[++cnt].u=u;
    e[cnt].v=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt;
}

inline void init(int n){
    for(int i=1;i<=n;i++) fa[i]=i;
}

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

inline void unite(int x,int y){
    fa[find(x)]=find(y);
}
int ccnt,f[200005];
inline void kruskal(){
    sort(e+1,e+1+m,cmp);
    for(int i=1;i<=m;i++){
        int eu=e[i].u,ev=e[i].v;
        if(find(eu)==find(ev)) continue;
        unite(eu,ev);
        anss+=e[i].w;
        f[++ccnt]=e[i].w;
    }
}
set<int> se;
int main(){
    cin>>n>>m>>k;
    init(n);
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        addedge(u,v,w);
    }
    kruskal();
    int bc=0;
    for(int i=1;i<=n;i++){
        if(se.count(find(i))==0){
            se.insert(find(i));
            bc++;
        }
    }
    if(k<bc){
        cout<<"No Answer"<<endl;
        return 0;
    }else{
        int num=k-bc;
        while(num--){
            anss-=f[ccnt];
            ccnt--;
        }
        cout<<anss<<endl;
    }
    return 0;
}

未完待续。。。

算法
最小生成树 并査集 图论

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！