脚本宝典收集整理的这篇文章主要介绍了最小生成树，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

题目链接

P3366 【模板】最小生成树

---

【模板】最小生成树

题目描述

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。

输入格式

第一行包含两个整数 (N,M)，表示该图共有 (N) 个结点和 (M) 条无向边。

接下来 (M) 行每行包含三个整数 (X_i,Y_i,Z_i) ，表示有一条长度为 (Z_i) 的无向边连接结点 (X_i,Y_i)。

输出格式

如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。

输入

4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

输出

7

说明/提示

数据规模：

对于 (20%) 的数据，(Nle 5，MLe 20)。

对于 (40%) 的数据，(Nle 50，Mle 2500)。

对于 (70%) 的数据，(Nle 500，Mle 10^4)。

对于 (100%) 的数据：(le Nle 5000，1le Mle 2times 10^5 ，1le Z_i le 10^4)。

PRim

• @R_876_1304@：(O(n^2))

代码

#include<bITs/stdc++.h>
using namespace std;
const int N=5005,inf=0x3f3f3f3f;
int a[N][N];
int d[N];
bool v[N];
int n,m;
int prim()
{
    memset(d,0x3f,sizeof d);
    int res=0;
    d[1]=0;
    for(int i=1;i<=n;i++)
    {
        int x=0;
        for(int j=1;j<=n;j++)
            if(!v[j]&&(x==0||d[j]<d[x]))x=j;
        if(d[x]==inf)return inf;
        v[x]=true;
        res+=d[x];
        for(int j=1;j<=n;j++)
            d[j]=min(d[j],a[x][j]);
    }
    return res;
}
int main()
{
    memset(a,0x3f,sizeof a);
    scanf("%d%d",&amp;n,&;m);
    for(int i=1;i<=n;i++)a[i][i]=0;
    while(m--)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        a[x][y]=a[y][x]=min(a[x][y],z);
    }
    int res=prim();
    if(res==inf)
        puts("orz");
    else
        printf("%d",res);
    return 0;
}

kruskal

• 时间复杂度：(O(mLOGm))

代码

#include<bits/stdc++.h>
using namespace std;
const int N=5005,M=2e5+10;
struct rec
{
    int x,y,z;
    bool operator<(rec &other)
    {
        return z<other.z;
    }
}Edge[M];
int fa[N];
int n,m,s,cnt;
int res;
bool v[N];
int get(int x)
{
    if(x==fa[x])return x;
    return fa[x]=get(fa[x]);
}
void kruskal()
{
    sort(edge,edge+m);
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=0;i<m;i++)
    {
        int x=get(edge[i].x),y=get(edge[i].y),w=edge[i].z;
        if(x==y)continue;
        cnt++;
        res+=w;
        fa[x]=y;
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].z);
        v[edge[i].x]=v[edge[i].y]=true;
    }
    kruskal();
    if(cnt==n-1)
        printf("%d",res);
    else
        puts("orz");
    return 0;
}

脚本宝典总结

以上是脚本宝典为你收集整理的最小生成树全部内容，希望文章能够帮你解决最小生成树所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。