最小生成树

· · 题解

在这里看本文章,效果更佳。
对于最小生成树的定义：在一个有n个点的图中，用n - 1条边将其连成一棵树，使得所有n - 1条边的权值之和最小。
最小生成树有两种做法：Prim和Kruskal，本文章两个都会介绍。

Prim：
前置知识：堆
Prim的做法就是把点分为已经加入最小生成树的和未被加入的，每次把距离已加入的点最近的边加入最小生成树。不过记录边比较麻烦，我们可以记录点，记v_i为节点i到已加入部分最短的边的长度，而小根堆记录v_i和i：

  1. 首先随便找一个点（一般选1号点）入小根堆。
  2. 每次取出堆顶u并pop。
  3. 判断u是否已经加入最小生成树
  4. 如果不是，将v_u加入最小生成树的边权和
  5. 然后遍历所有连接的点x，
  6. 若v_x>v_u，则将x加入堆。
  7. 重复2,3,4,5,6直到堆为空或者已经加入了n-1条边

关于无法形成一个树：该情况就是在结束后判断n个点是否都已经被标记，或者由于记录了边的条数，也可以判断边数是否为1。

code:

#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,cnt,ans;
int v[5005];
bool f[5005];//f判断该节点是否已经加入最小生成树
struct node
{
    int first,second;
    friend bool operator<(node x,node y){return x.first>y.first;}
};
priority_queue<node>q;//小根堆
struct graph
{
    int tot;
    int hd[5005];
    int nxt[400005],to[400005],dt[400005];
    void add(int u,int v,int w)
    {
        tot++;
        nxt[tot]=hd[u];
        hd[u]=tot;
        to[tot]=v;
        dt[tot]=w;
        return ;
    }
}g;//链式前向星存图
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        g.add(u,v,w);
        g.add(v,u,w);
    }
    memset(v,0x3f,sizeof(v));
    q.push((node){0,1});
    v[1]=0;//入堆第一个点
    while(!q.empty()&&cnt<n-1)//cnt记录边的条数，若堆不为空或边数不足n-1则继续
    {
        int xx=q.top().second;//取出堆顶
        q.pop();//弹出
        if(!f[xx])//若还未加入最小生成树
        {
            f[xx]=true;//标记为加入
            cnt++;//边数+1
            ans+=v[xx];//记录长度
            for(int i=g.hd[xx];i;i=g.nxt[i])//遍历能到达的点
                if(v[g.to[i]]>g.dt[i])//满足条件
                {
                    v[g.to[i]]=g.dt[i];//先更改v
                    q.push((node){v[g.to[i]],g.to[i]});//然后入堆
                }
        }
    }
    for(int i=1;i<=n;i++)
        if(!f[i])
        {
            printf("orz");
            return 0;
        }//判断是否连通
    printf("%d",ans);
    return 0;
}

Kruskal：
前置知识：并查集
Kruskal的做法：

  1. 把所有边按顺序排序。
  2. 从第一条边开始枚举。
  3. 如果边的两端联通（用并查集判断），就跳过。
  4. 否则就加入这条边，并合并两个端点的集合。
  5. 重复3,4步直到枚举完。

关于无法形成一个树：判断是否所有点都在同一个集合里。

code：

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,ans;
struct node
{
    int f,t,d;
}a[200005];//存边，Kruskal不用建图
bool cmp(node x,node y){return x.d<y.d;}
struct bin
{
    int w[5005];
    int find(int x)
    {
        if(x==w[x]) return x;
        w[x]=find(w[x]);
        return w[x];
    }
    void add(int x,int y)
    {
        w[find(x)]=find(y);
        return ;
    }
    bool ask(int x,int y)
    {
        if(find(x)==find(y)) return true;
        else return false;
    }
}b;//并查集
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i].f,&a[i].t,&a[i].d);
    for(int i=1;i<=n;i++) b.w[i]=i;//并查集初始化
    sort(a+1,a+m+1,cmp);//按边权排序
    for(int i=1;i<=m;i++)//枚举每条边
    {
        if(b.ask(a[i].f,a[i].t)) continue;//连通则跳过
        ans+=a[i].d;//否则记录
        b.add(a[i].f,a[i].t);//改为连通
    }
    for(int i=2;i<=n;i++)
        if(!b.ask(1,n))
        {
            printf("orz");
            return 0;
        }//判断是否连通
    printf("%d",ans);
    return 0;
}