小企业网站建设哪些好办,中企动力的网站如何,佛山制作手机网站,成都专业网站推广公司算法思路#xff1a;
将所有边按照权值的大小进行升序排序#xff0c;然后从小到大一一判断。
如果这个边与之前选择的所有边不会组成回路#xff0c;就选择这条边分#xff1b;反之#xff0c;舍去。
直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。
筛选出来的边…算法思路
将所有边按照权值的大小进行升序排序然后从小到大一一判断。
如果这个边与之前选择的所有边不会组成回路就选择这条边分反之舍去。
直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。
筛选出来的边和所有的顶点构成此连通网的最小生成树。 判断是否会产生回路的方法为使用并查集。
在初始状态下给各个个顶点在不同的集合中。
遍历过程的每条边判断这两个顶点的是否在一个集合中。
如果边上的这两个顶点在一个集合中说明两个顶点已经连通这条边不要。如果不在一个集合中则要这条边。 //kruskal求最小生成树
#includeiostream
#includealgorithm
using namespace std;
const int N 2e5 9;struct Edge
{int a, b, w;bool operator (const Edge W) const{return w W.w;}
} edges[N];int n, m, p[N], res, cnt;int find(int x)
{if (p[x] ! x) p[x] find(p[x]);return p[x];
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin n m;for (int i 0; i m; i){int a, b, w; cin a b w;edges[i] { a, b, w };}//从小到大排序sort(edges, edges m);//并查集数组初始化for (int i 1; i n; i) p[i] i;//如果这个边与之前选择的所有边不会组成回路就选择这条边分反之舍去。//判断是否会产生回路的方法为使用并查集。//每次将未加入的边加入到集合中去for (int i 0; i m; i){int a edges[i].a, b edges[i].b, w edges[i].w;//不在一个集合里面a find(a), b find(b);if (a ! b){res w;cnt;p[a] b;//加入集合}}//如果集合中的边数小于n - 1说明不存在最小生成树if (cnt n - 1) cout impossible;else cout res;return 0;
}关于并查集可以看一下我写的这个篇文章 http://t.csdnimg.cn/ClmtA
