【次小生成树】PAT (Top Level) 1016 Uniqueness of MST (35)

Think:
1知识点：次小生成树
2题意：
（1）：若最小生成树存在且唯一，第一行输出最小生成树权值和，第二行输出Yes
（2）：若最小生成树存在且不唯一，第一行输出最小生成树权值和，第二行输出No
（3）：若最小生成树不存在即图不连通，第一行输出”No MST”，第二行输出连通块数量
3反思：
（1）：次小生成树代码实现部分i与j不要混淆
（2）：次小生成树代码实现部分试探标记不要忘记当前边试探完成之后及时取消

PAT题集-题目链接

以下为Accepted代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct Edge{
int u, v, w;
int flag;
bool operator < (const Edge &b) const{
return w < b.w;
}
}edge[404014];
int f[504];
int tp, link[404014];
void init_f(int n);
int get_f(int x);
bool Merge(int x, int y);
int main(){
int n, m, num, sum;
while(~scanf("%d %d", &n, &m)){
for(int i = 0; i < m; i++){
scanf("%d %d %d", &edge[i].u, &edge[i].v, &edge[i].w);
edge[i].flag = 0;
}
sort(edge, edge+m);/*按边权升序排序*/
init_f(n);/*Kruskal算法并查集标记数组初始化初始化*/
tp = 0, num = 0, sum = 0;/*路径记录变量以及Kruskal算法记录变量初始化*/
for(int i = 0; i < m; i++){
if(Merge(edge[i].u, edge[i].v)){
num++;
sum += edge[i].w;
link[tp++] = i;
if(num == n-1) break;
}
}
if(num != n-1){
int cnt = 0;
for(int i = 1; i <= n; i++){
if(f[i] == i) cnt++;/*查询图内有几个连通块*/
}
printf("No MSTn");
printf("%dn", cnt);/*输出图内连通块的数量*/
}
else {
printf("%dn", sum);
int i, id, cnt, tmp;
for(i = 0; i < tp; i++){
id = link[i];
edge[id].flag = 1;/*标记试探边*/
/*Kruskal算法*/
init_f(n);
cnt = 0, tmp = 0;
for(int j = 0; j < m; j++){
if(edge[j].flag == 0){/*判断当前边是否为试探边*/
if(Merge(edge[j].u, edge[j].v)){/*尝试下标为j的边是否可以加入当前的生成树*/
cnt++;
tmp += edge[j].w;/*反思：j不要与i混淆写错*/
if(cnt == n-1) break;
}
}
}
edge[id].flag = 0;/*试探边试探完成之后取消试探标记*/
if(cnt == n-1 && tmp == sum) break;/*判断最小生成树是否唯一*/
}
if(i < tp) printf("Non");/*提前终止代表最小生成树不唯一*/
else printf("Yesn");
}
}
return 0;
}
void init_f(int n){
for(int i = 0; i <= n; i++){
f[i] = i;
}
return;
}
int get_f(int x){
if(x == f[x]) return x;
return f[x] = get_f(f[x]);
}
bool Merge(int x, int y){
int t1 = get_f(x);
int t2 = get_f(y);
if(t1 != t2){
f[t2] = t1;
return true;
}
return false;
}

最后

以上就是无奈鱼为你收集整理的【次小生成树】PAT (Top Level) 1016 Uniqueness of MST (35)的全部内容，希望文章能够帮你解决【次小生成树】PAT (Top Level) 1016 Uniqueness of MST (35)所遇到的程序开发问题。

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