进阶实验6-3.6 最小生成树的唯一性

题目链接
思路:这题要求取最小生成树的唯一性.那么最小生成树在什么情况下不唯一呢,当我们用kruskal算法构建最小生成树时,即把所有边按照权值从小到大一次排列,每次从中取不会令当前已建好的树形成回路的边,当我们发现有多条最优权值的边有相同的连接效果,即边两边连接的集合相同,即可知道最小生成树不唯一.比如现在已建好的树有两集合,1-3-5和2-4-6,此时有多条边有相同的最优权值且可连接两集合形成1-2-3-4-5-6的连通集,则最小生成树不唯一.
注意:我使用的并查集中存负数的节点为根节点,其值为该集合的元素数,其数组下标为根.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX = 1000005;
const int POINT = 501;
int W;//总权值
struct Edge {
int v, t, weight;
Edge(int a, int b, int c) { v = a; t = b; weight = c; }
}*e[MAX];
int k;
int root[POINT];
void union_root(int x,int y);
int find_root(int x);
bool Mst_is_unique(int M);//最小生成树是否唯一
int Getconnections(int N);//计算连通集数量
void init();//初始化并查集
bool cmp(Edge* A, Edge* B);
int main() {
int N, M;
int v, t, weight,cnt;
init();
scanf("%d%d", &N, &M);
for (int i = 0; i < M; i++) {
scanf("%d%d%d", &v, &t, &weight);
e[k++] = new Edge(v, t, weight);
union_root(v, t);
}
if ((cnt=Getconnections(N))==1) {
bool f1 = Mst_is_unique(M);
printf("%dn", W);
if (f1)
printf("Yesn");
else
printf("Non");
}
else
printf("No MSTn%d",cnt);
}
void union_root(int x, int y) {
x = find_root(x);
y = find_root(y);
if (x!=y) {
if (x < y) {
root[x] += root[y];
root[y] = x;
}
else {
root[y] += root[x];
root[x] = y;
}
}
}
int find_root(int x) {
return root[x] < 0 ? x : root[x] = find_root(root[x]);
}
bool Mst_is_unique(int M) {
bool f = true;
sort(e, e + M, cmp);
init();
for (int i = 0; i < M; i++) {
int v = e[i]->v, t = e[i]->t,w=e[i]->weight;
int f1 = find_root(v), f2 = find_root(t);
if (f1 != f2) {//两端点不属于同一集合,则加入树中不构成回路,加入之
if (f) {
for (int j = i + 1; j < M; j++) {
if (e[j]->weight != w)
break;
int v1 = e[j]->v, t1 = e[j]->t;
int
f3 = find_root(v1), f4 = find_root(t1);
if (f1 == f3 && f2 == f4 || f2 == f3 && f1 == f4)
f = false;
}
}
union_root(f1, f2);
W += w;
}
}
return f;
}
void init() {
for (int i = 0; i < POINT; i++)
root[i] = -1;
}
int Getconnections(int N) {
int cnt = 0;
for (int i = 1; i <= N; i++)
if (root[i] < 0)//值小于0的根节点数量
cnt++;
return cnt;
}
bool cmp(Edge* A, Edge* B) {
return A->weight < B->weight;
}

最后

以上就是着急钢铁侠为你收集整理的进阶实验6-3.6 最小生成树的唯一性的全部内容，希望文章能够帮你解决进阶实验6-3.6 最小生成树的唯一性所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。