POJ1679-判断MST是否唯一

傷城~ 2022-07-11 05:39 176阅读 0赞

The Unique MST

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;10000K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;29027</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;10372</td> 
  </tr> 
 </tbody> 
</table>

Description

Given a connected undirected graph, tell if its minimum spanning tree is unique.   
  
Definition 1 (Spanning Tree): Consider a connected, undirected graph G = (V, E). A spanning tree of G is a subgraph of G, say T = (V', E'), with the following properties:   
1. V' = V.   
2. T is connected and acyclic.   
  
Definition 2 (Minimum Spanning Tree): Consider an edge-weighted, connected, undirected graph G = (V, E). The minimum spanning tree T = (V, E') of G is the spanning tree that has the smallest total cost. The total cost of T means the sum of the weights on all the edges in E'.

Input

The first line contains a single integer t (1 <= t <= 20), the number of test cases. Each case represents a graph. It begins with a line containing two integers n and m (1 <= n <= 100), the number of nodes and edges. Each of the following m lines contains a triple (xi, yi, wi), indicating that xi and yi are connected by an edge with weight = wi. For any two nodes, there is at most one edge connecting them.

Output

For each input, if the MST is unique, print the total cost of it, or otherwise print the string 'Not Unique!'.

Sample Input

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

Sample Output

3
    Not Unique!

**题目大意：给你一张联通图，判断最小生成树是否唯一，如果唯一输出值，否则输出“Not Unique!” **

**题目思路：这题有很多方法，第一种是先求一遍普利姆，然后删去其中一条边在求次普利姆看权值是否相同，这个复杂度是0(n^3) 第二种是用克鲁斯卡尔，先求一遍克鲁斯卡尔然后把边都标记，然后sort一下，规则为如果值相同就把标记过后的边放在前面，再求一遍克鲁斯卡尔，如果出现了没有被标记的边说明不唯一，这个时间复杂度为O(n\*logn)但是常数比较大，当然还有大神用prim的n^2的算法，就是prim时求出每两个点之间的最短距离，最后再判断是否唯一，我这里用的是第二种方法！**

AC代码：

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    
    using namespace std;
    
    struct st{
       int u,v,w,flag;
    }s[20000];
    
    bool cmp(st a,st b){
        if(a.w==b.w)return a.flag<b.flag;
        return a.w<b.w;
    }
    int n,m;
    
    int pre[105];
    
    int get(int x){
       if(x!=pre[x])return pre[x] = get(pre[x]);
       return pre[x];
    }
    
    void klu(bool is){
         for(int i=1;i<=n;i++)pre[i]=i;
         sort(s,s+m,cmp);
         int num = 0;
         int flag = 0;
         int ans = 0;
         for(int i=0;i<m;i++){
            int x = get(s[i].u);
            int y = get(s[i].v);
            if(x!=y){
                pre[x] = y;
                num++;
                ans+=s[i].w;
                if(is){
                    if(!s[i].flag){flag=1;break;}
                }
                s[i].flag = 1;
            }
            if(num==n-1)break;
         }
         if(is){
            if(flag)printf("Not Unique!\n");
            else printf("%d\n",ans);
         }
    }
    
    int main()
    {
        int t;cin>>t;
        while(t--){
            scanf("%d%d",&n,&m);
            for(int i=0;i<m;i++){
                scanf("%d%d%d",&s[i].u,&s[i].v,&s[i].w);
                s[i].flag = 0;
            }
            klu(0);
            klu(1);
        }
        return 0;
    }