当前位置: 首页 > news >正文

企业网站建设预算方案网站项目遇到的问题

企业网站建设预算方案,网站项目遇到的问题,wordpress设置积分阅读,网络营销方案简述一.介绍 Kruskal(克鲁斯卡尔)算法是一种用于解决最小生成树问题的贪心算法。最小生成树是指在一个连通无向图中,选择一棵包含所有顶点且边权重之和最小的树。 下面是Kruskal算法的基本步骤: 将图中的所有边按照权重从小到大进行…

一.介绍

 Kruskal(克鲁斯卡尔)算法是一种用于解决最小生成树问题的贪心算法。最小生成树是指在一个连通无向图中,选择一棵包含所有顶点且边权重之和最小的树。

下面是Kruskal算法的基本步骤:

  1. 将图中的所有边按照权重从小到大进行排序
  2. 创建一个空的最小生成树集合(并查集实现)
  3. 遍历排序后的边,依次将边加入最小生成树集合中,但要确保加入的边不会形成环路。
    • 如果加入边后不会形成环路,则将该边加入最小生成树集合。
    • 如果加入边后会形成环路,(即在同一集合)则跳过该边。
  4. 重复步骤3,直到最小生成树集合中的边数等于图中顶点数减1,或者遍历完所有边。
  5. 最终得到的最小生成树集合即为所求的最小生成树。

Kruskal算法的核心思想是通过不断选择权重最小的边,并判断是否形成环路来构建最小生成树。它不需要事先知道图的连通性,而是通过边的选择来逐步连接图中的顶点,直到所有顶点都被连接为止。

需要注意的是,Kruskal算法适用于解决无向图的最小生成树问题,对于有向图则需要使用其他算法,如Prim算法。此外,Kruskal算法也可以处理带有边权重相同的情况。


二.模板题

P3366 【模板】最小生成树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)


三.【AC】代码

#include<bits/stdc++.h>
#define maxn 200010
using namespace std;
inline int read(){int ans=0,f=1;char cc=getchar();while(cc<'0' || cc>'9'){if(cc=='-') f=-1;cc=getchar();}while(cc>='0' && cc<='9'){ans=(ans<<1)+(ans<<3)+(cc-'0');cc=getchar();}return ans*f;
}
int n,m,ans=0;
bool flag=0;
int fa[5010];
struct Edge{int u,v,w;
}edge[maxn];
bool cmp(Edge a,Edge b){return a.w<b.w;
}
inline int find(int x){return x==fa[x] ? x : fa[x]=find(fa[x]);
}
inline void merge(int x,int y){int fx=find(x),fy=find(y);fa[fx]=fy;
}
void kruskal(){sort(edge+1,edge+m+1,cmp);int cnt=0;for(int i=1;i<=m;i++){int x=edge[i].u,y=edge[i].v;if(find(x)==find(y)) continue;ans+=edge[i].w;merge(x,y);cnt++;if(cnt==n-1){flag=1;return;} }
}
int main(){//读入数据 n=read();m=read();for(int i=1;i<=m;i++){edge[i].u=read();edge[i].v=read();edge[i].w=read();}for(int i=1;i<=n;i++) fa[i]=i;//调用算法 kruskal();//输出结果if(flag) printf("%d",ans); else printf("orz");return 0;
}

http://www.yayakq.cn/news/594706/

相关文章:

  • 小语种建站线在科技成都网站推广公司
  • 南通网站设计制作百度域名地址查询
  • 飘仙建站论坛wordpress文章手机平铺
  • 网上接单网站百度高级搜索指令
  • 做网站吗做企业网站对企业的好处
  • 模板手机网站建设公司排名创建全国文明城市总结
  • 做排行的网站做百度网站需不需要备案
  • 网站设计要考虑的因素深圳手机建网站
  • 罗湖装修公司网站建设室内装饰设计师证书有用吗
  • 浙江宏兴建设有限公司网站设计师网站十大网站排名
  • 网站有哪些费用多少钱建设网站是否需要一个主机
  • 成都哪里可以做网站360安全浏览器
  • 网站建设新模式wordpress评论点评
  • 常州外贸公司网站建设广州推广系统
  • 遵义网站建设1w1h三亚兼职网站
  • icp是网站备案兰州微信小程序开发公司
  • 电商网站怎么推广网站a记录的是做cname
  • 专业做网站安全的sine安中国政务网站建设绩效评估
  • 忻州建设网站的公司西安seo经理
  • 潍坊知名网站建设wordpress主题开发网站
  • 在什么网站做外贸做生存曲线网站
  • 做哪个网站比较有流量58同城兰州网站建设
  • 客户评价 网站建设开发公司名称推荐
  • 加盟网站制作推广四川淘宝网站建设方案
  • 11网站建设waocc西安有什么好玩的地方适合年轻人
  • 做水果网站弄个什么名字网站建设教育
  • 网站建设对电子商务中的作用北京招聘网站开发
  • 哈尔滨模板建站多少钱网站制作小工具
  • 专业深圳网站建设html网站支付链接怎么做的
  • 龙岩市建设局网站大学生创业做网站