企业官网建设流程全解析

成都网站外包公司,seo网络优化前景怎么样,四川建设厅官网查询官网,做网站费用怎么核算信奥赛C提高组csp-s之最小生成树算法Kruskal 一、Kruskal算法概述 Kruskal算法是一种用于求解最小生成树的贪心算法。最小生成树是一个无向连通图中#xff0c;连接所有顶点且边权总和最小的树。 特点#xff1a; 时间复杂度#xff1a;O(E log E)#xff0c;适合稀疏图…信奥赛C提高组csp-s之最小生成树算法Kruskal一、Kruskal算法概述Kruskal算法是一种用于求解最小生成树的贪心算法。最小生成树是一个无向连通图中连接所有顶点且边权总和最小的树。特点时间复杂度O(E log E)适合稀疏图基于边的贪心算法需要使用并查集数据结构二、算法原理核心思想将图中所有边按权值从小到大排序按顺序选择边如果这条边连接的两个顶点不在同一个连通分量中则将其加入最小生成树重复步骤2直到选择了n-1条边n为顶点数研究案例最小生成树题目说明给定一个无向图包含n nn个节点和m mm条边求最小生成树的权重和。如果图不连通输出orz。输入格式第一行两个整数n nn节点数和m mm边数接下来m mm行每行三个整数u , v , w u, v, wu,v,w表示节点u uu和v vv之间有一条权重为w ww的无向边输出格式一个整数最小生成树的权重和如果图不连通输出orz样例输入4 5 1 2 2 1 3 2 1 4 3 2 3 4 3 4 3样例输出7数据规模1 ≤ n ≤ 5000 1 \leq n \leq 50001≤n≤50001 ≤ m ≤ 2 × 10 5 1 \leq m \leq 2 \times 10^51≤m≤2×1051 ≤ w ≤ 10 4 1 \leq w \leq 10^41≤w≤104算法思路Kruskal算法边排序将所有边按权重从小到大排序并查集初始化每个节点自成一个集合贪心选择遍历排序后的边如果边的两个端点不在同一集合合并两个集合累加边权重计数已选边数连通性检查如果最终边数 ≠n − 1 n-1n−1输出orz代码实现#includebits/stdc.husingnamespacestd;intn,m;// n个顶点m条边// 边的结构体存储每条边的两个端点和权重structnode{intx,y,w;// 边连接的两个顶点x,y边的权重w}a[200010];// 最多200000条边// 比较函数用于将边按权重从小到大排序boolcmp(node a,node b){returna.wb.w;}intfa[5010];// 并查集数组用于记录每个顶点的父节点// 并查集的查找函数带路径压缩intfind(intx){if(fa[x]!x)returnfa[x]find(fa[x]);// 路径压缩returnfa[x];}// 并查集的合并函数voidunionSet(intx,inty){introotxfind(x);introotyfind(y);if(rootxrooty)return;// 已经在同一集合中不需要合并fa[rooty]rootx;// 合并两个集合}intmain(){cinnm;// 输入所有边的信息for(inti1;im;i){cina[i].xa[i].ya[i].w;}// 将边按权重从小到大排序sort(a1,am1,cmp);// 初始化并查集每个顶点自成一个集合for(inti1;in;i){fa[i]i;}intsum0;// 最小生成树的总权重intcnt0;// 已选边的数量// Kruskal算法核心遍历所有边for(inti1;im;i){// 如果当前边的两个端点不在同一连通分量中if(find(a[i].x)!find(a[i].y)){unionSet(a[i].x,a[i].y);// 合并两个连通分量suma[i].w;// 累加权重cnt;// 边数加1// 如果已选边数达到n-1说明最小生成树已完成if(cntn-1){coutsum;return0;}}}// 如果循环结束但边数不足n-1说明图不连通coutorz;return0;}功能分析算法步骤输入处理读取顶点数n、边数m以及所有边的信息边排序将所有边按权重从小到大排序并查集初始化每个顶点初始时都是一个独立的集合贪心选择按权重从小到大遍历每条边如果边的两个端点不在同一连通分量中选择该边合并这两个连通分量累加权重到总和中终止条件成功当选择了n-1条边时输出总权重失败如果遍历完所有边但边数不足n-1输出orz表示图不连通关键特点时间复杂度O(M log M)主要由排序决定空间复杂度O(N M)适用性适合稀疏图边数相对较少的情况正确性保证通过并查集确保不会形成环通过贪心选择保证权重最小各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}一、CSP信奥赛C通关学习视频课C语法基础C语法进阶C算法C数据结构CSP信奥赛数学CSP信奥赛STL二、CSP信奥赛C竞赛拿奖视频课信奥赛csp-j初赛高频考点解析CSP信奥赛C复赛集训课12大高频考点专题集训三、csp高频考点知识详解及案例实践CSP信奥赛C之动态规划CSP信奥赛C之标准模板库STL信奥赛C提高组csp-s知识详解及案例实践四、考级、竞赛刷题题单及题解GESP C考级真题题解CSP信奥赛C初赛及复赛高频考点真题解析CSP信奥赛C一等奖通关刷题题单及题解详细内容1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html4、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转CSP信奥赛C一等奖通关刷题题单及题解持续更新https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}