数据结构实验之图论六:村村通公路【Prim算法】(SDUT 3362)
2023-06-13 09:17:22 时间
题解:选点,选最小权的边,更新点权。可以手动自行找一遍怎么找到这个最小的生成树,随便选一个点放入我们选的集合中,然后看和这个点相连的点中,与那个点相连的那条边权值是最小的,选择之后,把相连的这个点一起放入集合中,这样的话集合中就多了一点,现在要找和这两个点都相连的点中,那个边的权最小,直到全部的点都在集合中就完成了。
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int inf = 0x3fffff;
int gra[1005][1005];
int vis[1005];
int dist[1005];
void prim(int n)
{
memset(vis,0,sizeof(vis));
for(int i = 0; i <= n; i ++) dist[i] = gra[1][i];
int Min = inf, v, flag = 1;
for(int i = 1; i <= n; i ++)
{
Min = inf;
for(int j = 1; j <= n; j ++)
{
if(!vis[j] && dist[j] < Min){
Min = dist[j];
v = j;
}
}
if(Min == inf) {flag = 0;break;}
vis[v] = 1;
for(int j = 1; j <= n; j ++)
{
if(!vis[j] && dist[j] > gra[v][j]){
dist[j] = gra[v][j];
}
}
}
int ans = 0;
for(int i = 1; i <= n;i ++)
{
ans += dist[i];
}
if(flag)printf("%d\n",ans);
else printf("-1\n");
}
int main()
{
int n,m,u,v,w;
while(~scanf("%d%d",&n,&m)){
for(int i = 0; i<= n; i ++)
{
for(int j = 0; j <= n; j ++)
{
if(i == j) gra[i][j] = 0;
else gra[i][j] = inf;
}
}
for(int i = 0; i < m; i ++)
{
scanf("%d%d%d",&u,&v,&w);
gra[u][v] = gra[v][u] = w;
}
prim(n);
}
return 0;
}
相关文章
- 数据结构与算法(三):双向链表[通俗易懂]
- 常用的算法和数据结构 面试_数据结构与算法面试题80道
- 算法与数据结构在我眼中的样子(1)排序算法
- 26·灵魂前端工程师养成-排序算法
- Java数据结构与算法(排序)——基数排序(LSD)
- 二叉树层次遍历算法——C/C++
- 【数据结构】— kmp算法和strstr函数
- 详解银行家算法「建议收藏」
- 《算法图解》-9动态规划 背包问题,行程最优化
- java中sort排序_数据结构算法总结
- 数据结构与算法之二叉搜索树
- 算法与数据结构之二叉树
- php弱类型花式绕过大全_协同过滤推荐算法代码
- 数据结构与算法Python_数据结构与算法python语言实现
- 数据结构与算法(一)-软件设计(十七)
- Go 数据结构和算法篇(六):选择排序
- Go 数据结构和算法篇(九):二分查找
- java 蛇形矩阵(算法)
- 查找组成一个偶数最接近的两个素数(算法)
- C/C++ 数据结构与算法笔记
- 数据结构实验之图论七:驴友计划【迪杰斯特拉算法】(SDUT 3363)
- 【数据挖掘】数据挖掘算法 组件化思想 示例分析 ( 组件化思想 | Apriori 算法 | K-means 算法 | ID3 算法 )
- Sentinel滑动时间窗限流算法原理及源码解析(下)
- Linux下安全加密:3DES算法(linux3des)
- 学习数据结构与算法分析如何帮助您成为更优秀的开发人员
- 传阿里唯一的P12算法专家,调入蚂蚁金服
- 从传感器和算法原理讲起,机器人是如何避障的丨雷锋网公开课
- asp下几种常用排序算法
- 微盾PHP脚本加密专家php解密算法
- PHP数据结构算法三元组Triplet
- 基于一致性hash算法(consistenthashing)的使用详解
- javascript实现playfair和hill密码算法