B3603 [图论与代数结构 301] 最短树问题_1 题解

ReverBer · 2021-07-25 11:29:39 · 题解

看到各位大佬都在用 Kruskal 算法，这里作为补充，再额外介绍一种求最小生成树的算法： Prim 算法。

前置知识：最小生成树——>指权值最小的生成树。

Prim 算法思想简介

Prim 算法的主要思想是每次选取一个点，作为根节点，之后依次寻找距离最近的点即可。Prim 算法适合稠密图。

寻找过程中的要点

• 每次都选取权值最小的边，但不能构成回路，构成环路的边则舍弃。
• 遇到权值相等，又均不构成回路的边，随意选择哪一条，均不影响生成树结果。
• 选取 n － 1 条恰当的边以连通 n 个顶点。

时间复杂度 O(n^2)。

CODE

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>pr;
int k,n,m,cnt,sum;
int head[5005],dis[5005];
bool vis[5005];
struct Edge{
    int v,w,next;
}e[400005];
void add(int u,int v,int w){//邻接表加边 
    e[++k].v=v;e[k].w=w;
    e[k].next=head[u];
    head[u]=k;
}priority_queue<pr,vector<pr>,greater<pr> >q;
void Prim(){
    dis[1]=0;
    q.push(make_pair(0,1));
    while(!q.empty()&&cnt<n){
        int d=q.top().first;//当前点进入点集的代价 
        int u=q.top().second;//当前点的编号 
        q.pop();
        if(vis[u])continue;
        cnt++;sum+=d;vis[u]=1;//累加与标记 
        for(int i=head[u];i!=-1;i=e[i].next)
            if(e[i].w<dis[e[i].v]){
                dis[e[i].v]=e[i].w;//如果松弛有效，加入待处理队列 
                q.push(make_pair(dis[e[i].v],e[i].v));
            }   
    }
}
int main(){
    memset(dis,127,sizeof(dis));
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);add(v,u,w);
    }Prim();
    printf("%d\n",sum);

    return 0;
}