POJ 1679 The Unique MST【最小生成树是否唯一】

今天药忘吃喽~ 2022-05-24 00:13 172阅读 0赞

## The Unique MST ##

Time Limit: 1000MS Memory Limit: 10000K  
Total Submissions: 34428 Accepted: 12558

#### 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!

解题分析：  
判断最小生成树是否唯一。先对图生成一个最小生成树，将用到的边全部标记为用过，然后将标记过的一条边暂时去掉，进行一遍kruskal，若还能生成一个最小生成树，则说明不唯一。依照此法将所有标记过的边都kruskal一遍。

AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    
    #define N 105
    
    struct node{
        int x, y, d, h;
    }s[N*N];
    
    int f[N];
    
    bool cmp(node a, node b)
    {
        return a.d < b.d;
    }
    
    int Find(int u)
    {
        if(f[u] == u) return u;
        f[u] = Find(f[u]);
        return f[u];    
    }
    
    bool Union(int u, int v)
    {
        int r1 = Find(u), r2 = Find(v);
        if(r1 != r2){
            f[r1] = r2;
            return true;
        }
        return false;
    }
    
    int Kruskal(int n, int t, int flag, int k)
    {
        int i, ans = 0, sum = 0;
        for(i = 0; i <= n; i++){
            f[i] = i;
        }
        for(i = 0; i < t && ans < n-1; i++){
            if(i == k){
                continue;
            }
            if(Union(s[i].x, s[i].y)){
                if(flag){
       //第一次的时候需要将参与最小生成树的路径标记，之后的不需要
                    s[i].h = 1;
                } 
                ans++;
                sum += s[i].d; 
            }
        }
        if(ans != n-1) return -1;//若该条路不是最小生成树但其权值和与最小生成树的和相等，也要继续进行判断
        return sum;
    }
    
    int main()
    {
        int i, j, n, t, ans, cout, T;
        scanf("%d", &T);
        while(T--){
            scanf("%d%d", &n, &t);
            for(i = 0; i < t; i++){
                scanf("%d%d%d", &s[i].x, &s[i].y, &s[i].d);
                s[i].h = 0;
            }
            sort(s, s+t, cmp);
            ans = Kruskal(n, t, 1, -1);
            for(i = 0; i < t; i++){
                if(!s[i].h) continue;//只用跑已经标记过的
                cout = Kruskal(n, t, 0, i);
                if(cout == ans){
                    break;
                }
            }
            if(i < t) printf("Not Unique!\n");
            else printf("%d\n", ans);
        }
        return 0;
    }