欢迎访问我的pat顶级题解目录哦 https://blog.csdn.net/richenyunqi/article/details/86751676

题目描述

算法设计

这是一道判断是否存在最小生成树，以及如果存在最小生成树是否唯一的题目，可以用Kruskal算法来解决。这里有两个问题需要进行判断：

• 是否存在最小生成树？如果不存在，则图中有几个连通块？
  这一点可以通过Kruskal算法最终得到的最小生成树中边的数量来确定。如果最终得到的最小生成树中边的数量等于图中结点数量-1，则存在最小生成树；否则不存在最小生成树，且连通块数量=图中结点数量-最终得到的最小生成树中边的数量
• 如果存在最小生成树，则其是否唯一？
  这里给出判定最小生成树不唯一的算法思路：

1. 在边的结构体中加入一个bool类型的域isTreeEdge标识该边能否成为最小生成树中的边，初始化为false，表示不能成为最小生成树中的边。
2. 对图中的每一组权值相同的边，进行两趟扫描，第一趟扫描，判断每条边能否成为最小生成树中的边并更新isTreeEdge域；第二趟扫描，如果当前扫描到的边的isTreeEdge域为true，然而此时该边不能加入最小生成树中，则最小生成树不唯一。

具体实现可见代码。

C++代码

#include<bits/stdc++.h>
using namespace std;
struct Edge{//边的类
int v1,v2,weight;
bool isTreeEdge;//标识该边能否成为最小生成树中的边
Edge(int vv1,int vv2,int w,bool is=false):v1(vv1),v2(vv2),weight(w),isTreeEdge(is) {}
};
vector<Edge>edges;
int n,m,father[505];//father为并查集
int findFather(int x){//查找并查集的根结点并进行路径压缩
if(x==father[x])
return x;
int temp=findFather(father[x]);
father[x]=temp;
return temp;
}
int main(){
scanf("%d%d",&n,&m);
while(m--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
edges.push_back(Edge(a,b,c));
}
sort(edges.begin(),edges.end(),[](const Edge&e1,const Edge&e2){
return e1.weight<e2.weight;
});//对边按权值排序
iota(father,father+n+1,0);//初始化并查集
int total=0,num=0;//最小生成树的权值、最小生成树中的边的数量
bool yes=true;//最小生成树是否唯一
for(int i=0,j=0;i<edges.size();i=j){//遍历edges
//扫描与edges[i]权值相等的边并判断该边能否成为最小生成树中的边
for(j=i;j<edges.size()&&edges[j].weight==edges[i].weight;++j)
if(findFather(edges[j].v1)!=findFather(edges[j].v2))
edges[j].isTreeEdge=true;
for(int k=i;k<j;++k){//扫描与edges[i]权值相等的边并插入到最小生成树中
int ua=findFather(edges[k].v1),ub=findFather(edges[k].v2);
if(ua!=ub){//边的两个结点不在一个集合中
total+=edges[k].weight;//递增权值
father[ua]=ub;//合并边的两个端点
++num;//递增最小生成树边的数量
}else if(edges[k].isTreeEdge)//如果边的两个结点在一个集合中而该边能成为最小生成树中的边
yes=false;//最小生成树不唯一
}
}
if(num==n-1)
printf("%dn%s",total,yes?"Yes":"No");
else
printf("No MSTn%d",n-num);
return 0;
}

最后

以上就是阔达砖头为你收集整理的pat顶级1016 Uniqueness of MST （35 point(s)）题目描述算法设计C++代码的全部内容，希望文章能够帮你解决pat顶级1016 Uniqueness of MST （35 point(s)）题目描述算法设计C++代码所遇到的程序开发问题。

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