最小生成树

定义

生成树：一张n个点的连通图中，选择n-1条边与n个点组成的树

最小生成树：即生成树中边权之和的最小者（可能存在多棵）

P3366 【模板】最小生成树

Prim算法 O(mlogm)

与Dijkstra非常类似

1. 将1号点放入生成树中并标记，同时更新与它相连的点的dis值
2. 选择未标记的点中dis最小的点，加入生成树中并标记
3. 使用与该点的连边更新相连点的dis
4. 重复2，3步，直到所有的点都被标记或所有未标记的点都无连边与已标记的点直接相连

所以，当标记的点的数量<点的总数量时，图不联通，无解

直接放代

#include<bits/stdc++.h>
using namespace std;
int inf=99999999999;
struct P{
	int dis,id;
    bool operator < (const  &that) const{
        return dis>that.dis;
    }
};//用优先队列来优化
struct node{
	int to,next,length;
}bian[200010];
int dis[5001],head[200010],k;
bool vis[5001];
void add(int u,int v,int w){
    bian[++k].to=v;
    bian[k].length=w;
    bian[k].next=head[u];
    head[u]=k;
}
int n,m,ans;
priority_queue<P> q;
int tot;//用来记录标记的点的数量
void prim(){
    for(int i=1;i<=n;i++)dis[i]=inf;
    dis[1]=0;
    q.push((P){0,1});
    while(!q.empty()){
        int u=q.top().id;
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        tot++;
        ans+=dis[u];
        for(int i=head[u];i;i=bian[i].next){
            int v=bian[i].to;
            if(dis[v]>bian[i].length){
                dis[v]=bian[i].length;
                q.push((P){dis[v],v});
            }
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    prim();
    if(tot==n)cout<<ans;
    else cout<<"orz";
    return 0;
}

Prim与Dijkstra求最短路的区别：

注意到代码的第38行

修改dis值，是保存它与其他点的连边的边长最小值

而最短路则是保存与起点的最短距离

最小生成树求的是边权之和

Kruskal算法 O(mlogm)

1. 将所有边从小到大排序
2. 将所有点放入各自的并查集中
3. 选择所有未使用边中边权最小的
4. 若该边所连接的两点已经联通(即成环)，则舍去，否则合并这两个并查集
5. 重复3，4步，直到所有的点都被标记或所有未标记的点都无连边与已标记的点直接相连

#include<bits/stdc++.h>
using namespace std;
struct node{
  int from.to,length;  
}bian[4000010];
int fa[10010],n,m,ans,cnt;
bool comp(node x,node y){
    return x.length<y.length;
}
int find(int x){
    if(x==fa[x])return x;
    return fa[x]=find(fa[x]);
}
void kruskal(){
    sort(bian+1,bian+m+1,comp);
    for(int i=1;i<=m;i++){
        int u=find(bian[i].from);
        int v=find(bian[i].to);
        if(u==v)continue;
        ans+=bian[i].length;
        fa[v]=u;
        cnt++;
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++)cin>>bian[i].from>>bian[i].to>>bian[i].length;
    kruskal();
    if(cnt==n-1)cout<<ans;
    else cout<<"orz";
}