[kuangbin带你飞]专题六最小生成树 K - The Unique MST （判断最小生成树是否唯一）...

Love The Way You Lie 2023-08-17 15:41 123阅读 0赞

# K - The Unique MST #

题目链接：[https://vjudge.net/contest/66965\#problem/K][https_vjudge.net_contest_66965_problem_K]

题目：

给定连接的无向图，告诉它的最小生成树是否唯一。  
  
    定义1（生成树）：考虑连通的无向图G =（V，E）。 G的生成树是G的子图，比如T =（V'，E'），具有以下属性：  
    1. V'= V.  
    2.T是连接的和非循环的。  
  
    定义2（最小生成树）：考虑边加权，连通，无向图G =（V，E）。 G的最小生成树T =（V，E'）是总成本最小的生成树。 T的总成本是指E'中所有边缘的权重之和。  
输入  
    第一行包含单个整数t（1 <= t <= 20），即测试用例的数量。每个案例代表一个图表。它以包含两个整数n和m（1 <= n <= 100），节点数和边数的行开始。以下m行中的每一行包含三元组（xi，yi，wi），表示xi和yi通过权重= wi的边连接。对于任何两个节点，最多只有一个边连接它们。  
产量  
    对于每个输入，如果MST是唯一的，则打印它的总成本，否则打印字符串'Not Unique！'。  
样本输入  
  
    2  
    3 3  
    1 2 1  
    2 3 2  
    3 1 3  
    4 4  
    1 2 2  
    2 3 2  
    3 4 2  
    4 1 2  
  
样本输出  
  
    3  
    Not Unique！

**思路：先 算出最小生成树，并用数组记录每一条边，然后枚举去掉这些边 看其是否也能构成最小生成树且值相同。而且 在删边之后，可能图构不成一棵树，要处理一下**

//
    // Created by hanyu on 2019/8/2.
    //
    #include <algorithm>
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <queue>
    #include <set>
    #include<math.h>
    using namespace std;
    typedef long long ll;
    const int maxn=2e6+7;
    int father[maxn];
    struct Node{
        int u,v,w;
        bool operator<(const Node &other)const{
            return this->w<other.w;
        }
    }node[maxn];
    int find(int x)
    {
        if(x==father[x])
            return x;
        return father[x]=find(father[x]);
    }
    int main()
    {
        int t;
        scanf("%d",&t);
        while(t--)
        {
            int n,m;
            scanf("%d%d",&n,&m);
            for(int i=0;i<m;i++)
                scanf("%d%d%d",&node[i].u,&node[i].v,&node[i].w);
            for(int i=0;i<=n;i++)
                father[i]=i;
            sort(node,node+m);
            int write[maxn],cnt=0,ans=0;
            for(int i=0;i<m;i++)
            {
                int uu=find(node[i].u);
                int vv=find(node[i].v);
                if(uu==vv)
                    continue;
                else
                {
                    father[uu]=vv;
                    write[cnt++]=i;//数组记录路径
                    ans+=node[i].w;
                }
            }//计算最小生成树
            int flag=1;
            for(int k=0;k<cnt;k++)//删去这cnt条边，再求最小生成树，判断该最小生成树与上面ans是否相同
            {
                for(int kk=0;kk<=n;kk++)
                {
                    father[kk]=kk;
                }
                int sum=0,hh=0;
                for(int i=0;i<m;i++)
                {
                    if(i==write[k])//该编号和记录的编号相同，则无需处理
                        continue;
                    int uuu=find(node[i].u);//求最小生成树
                    int vvv=find(node[i].v);
                    if(uuu==vvv)
                        continue;
                    else
                    {
                        father[uuu]=vvv;
                        sum+=node[i].w;
                        hh++;
                    }
                }
                if(hh==n-1&&sum==ans)
                {
                    flag=0;
                    break;
                }
            }
            if(flag)
                printf("%d\n",ans);
            else
                printf("Not Unique!\n");
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Vampire6/p/11288343.html

[https_vjudge.net_contest_66965_problem_K]: https://vjudge.net/contest/66965#problem/K