PTA 7-4 最小生成树的唯一性 (35分)

女爷i 2023-02-13 11:02 20阅读 0赞

# PTA 7-4 最小生成树的唯一性 (35分) #

给定一个带权无向图，如果是连通图，则至少存在一棵最小生成树，有时最小生成树并不唯一。本题就要求你计算最小生成树的总权重，并且判断其是否唯一。

## 输入格式： ##

首先第一行给出两个整数：无向图中顶点数 N（≤500）和边数 M。随后 M 行，每行给出一条边的两个端点和权重，格式为“顶点1 顶点2 权重”，其中顶点从 1 到N 编号，权重为正整数。题目保证最小生成树的总权重不会超过 2^30

## 输出格式： ##

如果存在最小生成树，首先在第一行输出其总权重，第二行输出“Yes”，如果此树唯一，否则输出“No”。如果树不存在，则首先在第一行输出“No MST”，第二行输出图的连通集个数。

## 输入样例 1： ##

5 7
    1 2 6
    5 1 1
    2 3 4
    3 4 3
    4 1 7
    2 4 2
    4 5 5

## 输出样例 1： ##

11
    Yes

## 输入样例 2： ##

4 5
    1 2 1
    2 3 1
    3 4 2
    4 1 2
    3 1 3

## 输出样例 2： ##

4
    No

## 输入样例 3： ##

5 5
    1 2 1
    2 3 1
    3 4 2
    4 1 2
    3 1 3

## 输出样例 3： ##

No MST
    2

## 【程序思路】 ##

用Kruskal算法创建最小生成树，如果最小生成树如果不唯一，那就说明最小生成树中的某条边可以换成其他一条同权值的边且保证仍然是最小生成树，如此只需要对最小生成树中权值不唯一的边进行删除并重新进行最小生成树的查找即可。

## 【程序实现】 ##

#include<bits/stdc++.h>
    using namespace std;
    int n,m,c = 0,num;
    struct edge {
        
        int u,v,w;
    }edg[130000];
    int parent[501],tag[130000],tn,flag;
    void init() {
        
        for(int i = 1;i <= n;i ++)
            parent[i] = i;
    }
    int getParent(int k) {
        
        return k == parent[k] ? parent[k] : (parent[k] = getParent(parent[k]));
    }
    bool cmp(const edge &a,const edge &b) {
        
        return a.w < b.w;
    }
    bool check() {
        
        for(int i = 0;i < tn;i ++) {
        
            init();
            int d = 0,e = 0;
            for(int j = 0;j < m;j ++) {
        
                if(j == tag[i]) continue;
                if(getParent(edg[j].u) != getParent(edg[j].v)) {
        
                    parent[getParent(edg[j].u)] = getParent(edg[j].v);
                    d += edg[j].w;
                    e ++;
                }
            }
            if(e == n - 1 && d == c) return true;
        }
        return false;
    }
    int main() {
        
        scanf("%d%d",&n,&m);
        init();//初始化parent数组
        for(int i = 0;i < m;i ++) {
        
            scanf("%d%d%d",&edg[i].u,&edg[i].v,&edg[i].w);
        }
        sort(edg,edg + m,cmp);//按权重从小到大排序
        for(int i = 0;i < m;i ++) {
        
            if(getParent(edg[i].u) != getParent(edg[i].v)) {
        
                parent[getParent(edg[i].u)] = getParent(edg[i].v);
                c += edg[i].w;
                if(i < m - 1 && edg[i].w == edg[i + 1].w || i && edg[i].w == edg[i - 1].w) {
        //有相同权重的边
                    flag = 1;
                    tag[tn ++] = i;
                }
            }
        }
        for(int i = 1;i <= n;i ++) {
        
            if(getParent(i) == i) num ++;
        }
        if(num != 1) printf("No MST\n%d",num);
        else printf("%d\n%s",c,!flag || !check() ? "Yes" : "No");
    }