搜索引擎是网站吗,html5网站的优点,大鱼号自媒体平台注册,公司的网址题目#xff1a;#xff08;来源#xff1a;AcWing#xff09;
给定一个 n 个点 m 条边的无向图#xff0c;图中可能存在重边和自环#xff0c;边权可能为负数。
求最小生成树的树边权重之和#xff0c;如果最小生成树不存在则输出 impossible。
给定一张边带权的无向…题目来源AcWing
给定一个 n 个点 m 条边的无向图图中可能存在重边和自环边权可能为负数。
求最小生成树的树边权重之和如果最小生成树不存在则输出 impossible。
给定一张边带权的无向图 G(V,E)其中 V 表示图中点的集合E 表示图中边的集合n|V|m|E|。
由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行每行包含三个整数 u,v,w表示点 u 和点 v 之间存在一条权值为 w 的边。
输出格式
共一行若存在最小生成树则输出一个整数表示最小生成树的树边权重之和如果最小生成树不存在则输出 impossible。
数据范围
1≤n≤105, 1≤m≤2∗105, 图中涉及边的边权的绝对值均不超过 1000。
输入样例
4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4输出样例
6
kruskal算法思路 每次联通一条最短边加n-1次 如果边的两给节点已经联通则无需再加。 查找两个点是否在同一个联通集合需要用到并查集 如果加入边的数量n-1则说明无法生成最小生成树。
代码实现
#includeiostream
#includealgorithm
using namespace std;const int N 100020,M 200020;//定义边
struct Edge{int a,b,w;bool operator(const Edge edge){return wedge.w;}
};int n,m;
int p[N];//并查集的集合
Edge edge[M];//边的集合int find(int x)//并查集的find函数
{if(p[x]!x) p[x]find(p[x]);//递归的同时压缩路径提高效率return p[x];//直接返回所在集合编号
}int kruskal()
{int res0,nums0;//res记录最小树权和num记录联通边数for(int i 0;im;i){Edge temp edge[i];int atemp.a , btemp.b , c temp.w;a find(a);b find(b);if(a ! b)//a,b不在一个联通集合中{p[b] a;//就把他们联通resc;//加入这个最短边nums;//联通边数1}}if(numsn-1) return -1;return res;}int main()
{cinnm;for(int i 1;in;i) p[i] i;//初始化并查集for(int i 0;im;i)//初始化边集{int x,y,z;scanf(%d%d%d,x,y,z);edge[i] {x,y,z};}//边集升序排序sort(edge,edgem);int t kruskal();if(t-1) cout impossibleendl;else couttendl;return 0;
}
参考
B站蓝不过海呀
地址 图-最小生成树-Prim(普里姆)算法和Kruskal(克鲁斯卡尔)算法_哔哩哔哩_bilibili
