判斷一個圖的最小生成樹是否唯一，可以求其次小生成樹。如果它的次小生成樹權值之和等於最小生成樹權值之和，則最小生成樹不唯一，否則最小生成樹唯一。

求次小生成樹我的方法是O(N^2 + M)的。首先求出最小生成樹，記錄權值之和爲MinST。然後枚舉添加邊(u,v)，加上以後一定形成一個環，找到環上非(u,v)邊的權值最大的邊，把它刪掉，計算當前生成樹的權值之和，取所有枚舉加邊後生成樹權值之和的最小值，就是次小生成樹。

實際上具體更簡單的方法爲從每個頂點i，遍歷整個最小生成樹，定義F[j]爲從i到j的路徑上最大邊的權值，用O(N)的方法求出每個F[j]。然後枚舉頂點i的鄰域，遍歷每條不再最小生成樹中的邊(i,j)，加上這條邊，並刪除環上最大邊(非(i,j))，新的生成樹權值之和爲MinST + w(i,j) - F[j]，記錄其最小值即可，時間複雜度爲O(N^2 + M)。求最小生成樹可以用最簡單的Prim，時間複雜度爲O(N^2)，用更好的算法是沒有意義的。

這種方法比起那種求出最小生成樹後，枚舉刪除最小生成樹上每條邊，然後再求最小生成樹的方法應該要快些，因爲那種方法的時間複雜度爲O(N ( N logN + M) )(Prim + Heap)。

/* 
 * Problem: pku1679 The Unique MST
 * Author: Guo Jiabao
 * Time: 2009.4.14 8:28
 * State: Solved
 * Memo: 次小生成樹 Prim
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=101,MAXM=MAXN*MAXN*4,INF=0x7FFFFFFF;
using namespace std;
struct edge
{
    edge *next,*op;
    int t,c;
    bool mst;
}ES[MAXM],*V[MAXN],*clst[MAXN],*NA[MAXN];
int N,M,EC,MinST,NMST,Ans;
int F[MAXN],MST[MAXN];
inline void addedge(edge **V,int a,int b,int c)
{
    ES[++EC].next=V[a];
    V[a]=ES+EC; V[a]->t=b; V[a]->c=c;
    ES[++EC].next=V[b];
    V[b]=ES+EC; V[b]->t=a; V[b]->c=c;
    V[a]->op=V[b]; V[b]->op=V[a];
    V[a]->mst=V[b]->mst=false;
}
void init()
{
    int i,a,b,c;
    scanf("%d%d",&N,&M);
    EC=-1;Ans=INF;MinST=0;
    memset(clst,0,sizeof(clst));
    memset(V,0,sizeof(V));
    memset(NA,0,sizeof(NA));
    for (i=1;i<=M;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        addedge(V,a,b,c);
    }
}
void prim()
{
    int i,j;
    for (i=1;i<=N;i++)
        MST[i]=INF;
    for (i=1;;)
    {
        MST[i]=-INF;
        for (edge *e=V[i];e;e=e->next)
        {
            if (e->c < MST[j=e->t])
            {
                MST[j]=e->c;
                clst[j]=e->op;
            }
        }
        int Mini=INF;i=0;
        for (j=1;j<=N;j++)
            if (MST[j]!=-INF && MST[j] < Mini)
            {
                Mini=MST[j];
                i=j;
            }
        if (i==0)
            break;
    }
    for (i=2;i<=N;i++)
    {
        MinST+=clst[i]->c;
        j=clst[i]->t;
        clst[i]->mst=true;
        clst[i]->op->mst=true;
        addedge(NA,i,j,clst[i]->c);
    }
}
void dfs(int i)
{
    for (edge *e=NA[i];e;e=e->next)
    {
        int j=e->t;
        if (F[j]==-INF)
        {
            F[j]=F[i];
            if (e->c > F[j])
                F[j]= e->c;
            dfs(j);
        }
    }
}
void smst()
{
    int i,j;
    for (i=1;i<=N;i++)
    {
        for (j=1;j<=N;j++)
            F[j]=-INF;
        F[i]++;
        dfs(i);
        for (edge *e=V[i];e;e=e->next)
        {
            j=e->t;
            if (!e->mst)
            {
                NMST=MinST + e->c - F[j];
                if (NMST < Ans)
                    Ans = NMST;
            }
        }
    }
}
int main()
{
    int T,i;
    freopen("umst.in","r",stdin);
    freopen("umst.out","w",stdout);
    scanf("%d",&T);
    for (i=1;i<=T;i++)
    {
        init();
        prim();
        smst();
        if (Ans > MinST)
            printf("%dn",MinST);
        else
            printf("Not Unique!n");
    }
    return 0;
}