数据结构实验之图论六:村村通公路 【克鲁斯卡尔算法】
2023-06-13 09:17:22 时间
分析:MST,用最好理解的克鲁斯卡尔算法,其中 fin 是寻找这个点的父节点并进行路径压缩,merge 是把这两个点合并在一起,表示现在已经是相连接的了,克鲁斯卡尔算法要求需要先对边权来排序,所以首先用个结构体来存 起点 - 终点 - 权值,然后按权值从大到小排序,依次选取最小边权。
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct node
{
int b,e;
int w;
}s[3005];
bool cmp(struct node a, struct node b)
{
return a.w < b.w;
}
bool vis[1005];
int c[10005];
int fin(int x)
{
int r = x;
while(r != c[r]){
r = c[r];
}
int i = x, j;
while(c[i] != r)
{
j = c[i];
c[i] = r;
i = j;
}
return r;
}
int merge(int x, int y)
{
if(fin(x) != fin(y))
{
c[fin(x)] = fin(y);
return 1;
}
return 0;
}
int main()
{
int n,m,ans = 0,cnt = 0;
while(~scanf("%d%d",&n,&m)){
for(int i = 0; i < m; i ++)
{
scanf("%d%d%d",&s[i].b,&s[i].e,&s[i].w);
}
for(int i = 0; i <= n; i ++)c[i] = i;
sort(s,s+m,cmp);
ans = 0;
cnt = 0;
for(int i = 0; i < m; i ++)
{
if(merge(s[i].b,s[i].e) == 1)
{
ans += s[i].w;
cnt ++;
}
if(cnt == n - 1) break;
}
if(cnt == n - 1)
{
printf("%d\n",ans);
}
else printf("-1\n");
}
return 0;
}
相关文章
- 数据结构b-树和b+树_A票领导B票算法
- 算法笔记汇总精简版下载_算法与数据结构笔记
- Dijkstra(迪杰斯特拉算法)的实现-------------------------C,C++,Matlab实现
- 数据结构与算法笔记
- 「数据结构与算法Javascript描述」链表
- 外网疯传!字节大佬闭关三月撰写的数据结构与算法笔记遭恶意开源
- 算法与数据结构之图
- 数据结构算法常见面试考题及答案_数据结构和算法面试题
- Go 数据结构和算法篇(九):二分查找
- Go 数据结构和算法篇(十八):平衡二叉树
- 【算法基础】冒泡排序
- 数据结构与算法
- DeepMind 发布强化学习通用算法 DreamerV3,AI 成精自学捡钻石
- 【数据结构与算法】图遍历算法 ( 深度优先搜索代码示例 )
- Java数据结构和算法(四)——栈详解编程语言
- Java数据结构和算法(一)——简介详解编程语言
- java 数据结构与算法—递归详解编程语言
- 火星上的甲烷从哪里来?科学家用算法给出了答案
- C#数据结构与算法揭秘二
- 最小树形图模板朱刘算法分享