我开始的思路是这样的：用prim算法去求最小生成树，如果在求树的过程中出现了多重选择（就是说某一步可以被加入的节点有复数个），则认为图中的树不唯一。后来发现这个算法是有问题的。
一个例子：
1
4 3
1 2 1
1 3 1
1 4 1
这是一个爪子的形状，图本身就是一颗树。如果把节点1作为起始节点，第一步就会出现多重选择的情况，然而它的最小生成树是唯一的。

正确的算法是：先求出一颗最小生成树，然后每次去掉树上的一个边，重新求最小生成树。如果某次求出的权值和最初的一样，说明最小生成树是不唯一的，因为你求出了两颗不一样的最小生成树。

我求MST的算法是prim，prim的复杂度是O(n^2)，最小生成树用n-1条边，所以最多要重新求n-1次最小生成树，所以整个算法的时间复杂度为O(n^3)。

代码写的很丑，拿出来望大家批评：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 105
#define INFINITY 2147483647

void prim1(int g[][MAX_SIZE],int n,int *vv,int edge[][3])
{
    int low[MAX_SIZE][2],v,min,i,k,top;
    char flag[MAX_SIZE];

    memset(flag,0,n);
    flag[0] = 1;
    for(i=0;i<n;i++)
    {
        low[i][0] = g[0][i];
        low[i][1] = 0;
    }
    v = 0;
    top = 0;

    for(k=1;k<n;k++)
    {
        //find min
        for(i=0;i<n;i++)
            if(!flag[i] && low[i][0]!=INFINITY)
                break;
        min = i;
        for(i=i+1;i<n;i++)
            if(!flag[i] && low[i][0]<low[min][0])
                min = i;

        //add min into mst
        flag[min] = 1;
        v += low[min][0];

        edge[top][0] = low[min][1];
        edge[top][1] = min;
        edge[top][2] = low[min][0];
        top++;

        //fix low
        for(i=0;i<n;i++)
            if(!flag[i] && g[min][i]<low[i][0])
            {
                low[i][0] = g[min][i];
                low[i][1] = min;
            }
    }

    *vv = v;
}

void prim2(int g[][MAX_SIZE],int n,int *vv)
{
    int low[MAX_SIZE],v,min,i,k;
    char flag[MAX_SIZE];

    memset(flag,0,n);
    flag[0] = 1;
    for(i=0;i<n;i++)
        low[i] = g[0][i];
    v = 0;

    for(k=1;k<n;k++)
    {
        //find min
        for(i=0;i<n;i++)
            if(!flag[i] && low[i]!=INFINITY)
                break;
        min = i;
        for(i=i+1;i<n;i++)
            if(!flag[i] && low[i]<low[min])
                min = i;

        //add min into mst
        flag[min] = 1;
        v += low[min];

        //fix low
        for(i=0;i<n;i++)
            if(g[min][i] < low[i])
                low[i] = g[min][i];
    }

    *vv = v;
}

int main()
{
    int T;
    int n,m;
    int i,j,k,w;
    int g[MAX_SIZE][MAX_SIZE];
    int v,vv;
    int edge[MAX_SIZE][3];

    scanf("%d",&T);
    while(T>0)
    {
        //构建原始图
        scanf("%d%d",&n,&m);

        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
                g[i][j] = INFINITY;

        for(i=0;i<n;i++)
            g[i][i] = 0;

        for(k=0;k<m;k++)
        {
            scanf("%d%d%d",&i,&j,&w);
            i--;
            j--;
            g[i][j] = w;
            g[j][i] = w;
        }

        //用prim求出一棵树
        prim1(g, n, &v, edge);

        //依次去掉树中的边，重新求树，看求出来的权值是否相同
        for(i=0;i<n-1;i++)
        {
            //去掉边
            g[edge[i][0]][edge[i][1]] = INFINITY;
            g[edge[i][1]][edge[i][0]] = INFINITY;

            //重新求树
            prim2(g, n, &vv);
            if(v==vv)
                break;

            //回复图
            g[edge[i][0]][edge[i][1]] = edge[i][2];
            g[edge[i][1]][edge[i][0]] = edge[i][2];
        }

        if(i==n-1)
            printf("%d\n",v);
        else
            printf("Not Unique!\n");

        T--;
    }

    return 0;
}