首页 > 其他分享 >最小生成树模板

最小生成树模板

时间:2024-01-26 17:33:18浏览次数:32  
标签:const 个点 int 最小 生成 edge 模板 dis

最小生成树

\(n\) 个点用 \(n-1\) 条边连接成一个连通块,形成的图形只可能是树

一个有 \(n\) 个点的连通图,边一定是大于等于 \(n-1\) 条的。图的最小生成树,就是在这些边中选择 \(n-1\) 条出来,连接所有的 \(n\) 个点。这 \(n-1\) 条边的边权之和是所有方案中最小的。

Prim算法

适用于稠密图,时间复杂度 \(O(n^2)\)

核心思想:每次挑一条与当前集合相连的最短边。

// vis[i] 表示点i是否在当前生成树集合中
// dis[i] 表示点i到当前集合的最短边的长度
// g[i][j] 表示点i和点j的边权
// 返回值:最小生成树中所有边的总长度
int Prim() {
    int mst = 0;
    memset(dis, 0x7f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[1] = 0; //选 1 当起点
    for (int i = 1; i < n; i++) {
        int k = -1, minn = INF;
        // 寻找最短边
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && dis[j] < minn) {
                k = j;
                minn = dis[j];
            }
        }
        vis[k] = true;
        mst += dis[k];
        // 用新加入的点 k 更新到邻接点的最短边
        for (int j = 1; j <= n; j++) {
            if (!vis[j]) dis[j] = min(dis[j], g[k][j]);
        }
    }
    return mst;
}

Kruskal算法

适用于稀疏图,时间复杂度 \(O(m\log m)\)

核心思想:按照边权升序排列,从小到大选边,如果不构成环,则加入mst,否则跳过。

const int N = 1e5 + 10;
const int M = 1e6 + 10;
//存边
struct Edge {
    int from, to, w;
    bool operator < (const Edge &A) const {
        return w < A.w;
    }
} edge[M];
int n, m; //n个点,m条边
int fa[N]; //并查集

//并查集初始化
void init() {
    for (int i = 1; i <= n; i++) fa[i] = i;
}

//递归找根结点,路径压缩
int find1(int x) {
    if (fa[x] != x) fa[x] = find1(fa[x]);
    return fa[x];
}

//非递归找根结点,路径压缩
int find2(int x) {
    int tmp = x, rt;
    while (fa[x] != x) x = fa[x];
    rt = x;
    x = tmp;
    while (fa[x] != x) {
        tmp = fa[x];
        fa[x] = rt;
        x = tmp;
    }
    return rt;
}

void kruskal() {
    int mst = 0, cnt = 0, k = 1, rx, ry;
    while (cnt < n-1) { //找 n-1 条边
        rx = find1(edge[k].from);
        ry = find1(edge[k].to);
        if (rx != ry) {
            mst += edge[k].w;
            fa[rx] = ry;
            cnt++;
        }
    }
    cout << mst << endl;
}

int main() {
    cin >> n >> m; //输入点数、边数
    int from, to, w;
    init();
    for (int i = 1; i <= m; i++) {
        cin >> edge[i].from >> edge[i].to >> edge[i].w;
    }
    sort(edge+1, edge+1+m);
    kruskal();
    return 0;
}

标签:const,个点,int,最小,生成,edge,模板,dis
From: https://www.cnblogs.com/kuangbiaopilihu/p/17989860

相关文章

  • kubeadm生成集群时指定所有证书过期时间为99年
    使用kubeadm初始化Kubernetes集群时生成99年有效期的所有证书,可以通过以下步骤操作:编辑kubeadm的配置文件kubeadm-config.yaml:apiVersion:kubeadm.k8s.io/v1beta2kind:ClusterConfigurationapiServer:extraArgs:certificate-duration:868320hcertifica......
  • 生成nginx证书
    生成NginxSSL证书的基本步骤如下:准备证书签发请求文件(CSR--即证书签名申请(CertificateSigningRequest)):opensslreq-new-nodes-sha256-newkeyrsa:2048-keyoutserver.key-outserver.csrOrganizationName:公司名称,可以是中文或英文。OrganizationalUnitName:部门......
  • 【模板】可持久化线段树 2
    就是区间第k大,原题链接这个是用整体二分做的这个是用可持久化线段树做的线段树还是快一点啊#include<bits/stdc++.h>#definelllonglongusingnamespacestd;inlinellread(){ charc=getchar();lla=0,b=1; for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1; ......
  • # 生成指定列名行索引的空表格 # 修改字典内不同表格的值
    #生成指定列名行索引的空表格#修改字典内不同表格的值importpandasaspdlist1=['列1','列2','列3']#列名列表list2=['行1','行2','行3']#行索引列表df=pd.DataFrame(columns=list1,index=list2)#1dic={key:dffork......
  • 【译】生成考古学:人工智能创建古代世界的真实图像
    原作:Ming引子:历史令人着迷,但很难想象几千年前的世界是什么样子。 许多方面造成了这一困难。部分原因是古代人有不同的审美观。在1400年代之前,画家很少考虑透视,使得事物的比例在现代人看来相当奇怪。部分原因是时间已经腐蚀掉了文物中的很多细节。陶器、雕塑和建筑物随着时间......
  • python中利用变量解压列表、元组、字符串、字典、文件对象、迭代器和生成器等序列
    一、如果知道序列中元素的个数,可以直接进行变量赋值。coords=(102,40)lon,lat=coordsprint(lon)print(lat)text="news"a,b,c,d=textprint(a)print(b)print(c)print(d)二、如果不知道序列中元素的个数,可以通过*变量名来代表多个元素的变量,无论序列是什......
  • 模板
    #definesandomsigned#definefre(x,y)freopen(#x".in","r",stdin),freopen(#y".out","w",stdout);#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include&l......
  • 自定义模板中数据标签
    笔记数据标签(DataTag)只是一种辨识度比较高的文本字符串,样式完全由开发人员自己说了算。比如这样的数据标签“【##日期$$】”,编写代码openDataTag("【##日期$$】")即可返回数据标签对象,进而可以对此数据标签填充数据或设置样式等操作。在实际的Word文档开发中,经常需要自动填充......
  • (2/60)有序数组平方、长度最小子数组、螺旋矩阵
    有序数组的平方leetcode:977.有序数组的平方给你一个按非递减顺序排序的整数数组nums,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。暴力法思路遍历数组,元素原地替换为自身平方值。将数组进行排序。复杂度分析时间复杂度:O(N+logN)空间复杂度:O(1)注......
  • 代码随想录算法训练营第二天|977.有序数组的平方 ,209.长度最小的子数组 ,59.螺旋矩阵II
    977.有序数组的平方给你一个按非递减顺序排序的整数数组nums,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。题目链接:https://leetcode.cn/problems/squares-of-a-sorted-array/错误的vector遍历方式,这会导致访问越界!!!while(nums[flag]<0)flag++;倒也不难,我......