题目大意： 问一个图的最小生成树是不是唯一的

QAQ prim计算最小生成树的同时，记录最小生成树里面两点间的权值最大的边

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
int T,n,m;
int a[1010][1010],pre[1010],d[1010];
bool vis[1010];
int maxd[1010][1010];

int prim(int s)
{
    int sum = 0,tmp;
    memset(vis,0,sizeof(vis));
    for(int i = 1;i <= n; ++i)
        d[i] = a[s][i],pre[i] = s;
    vis[s] = 1;
    d[s] = 0;
    for(int i = 1;i < n; ++i)
    {
        int mincost = INF;
        for(int j = 1;j <= n; ++j)
            if(!vis[j] && mincost > d[j])
                mincost = d[j],tmp = j;
        for(int j = 1;j <= n; ++j)
            if(vis[j])
                maxd[tmp][j] = maxd[j][tmp] = max(mincost,maxd[pre[tmp]][j]);
        vis[tmp] = 1;
        sum += mincost;
        for(int j = 1;j<= n; ++j)
        {
            if(!vis[j] && d[j] > a[tmp][j])
                d[j] = a[tmp][j],pre[j] = tmp;
        }
    }
    return sum;
}

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        memset(a,0x3f,sizeof(a));
        for(int i = 0;i <= n; ++i)
            a[i][i] = 0;
        for(int i = 0;i < m; ++i)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            a[x][y] = a[y][x] = z;
        }
        int sum = prim(1);
        int lsum = INF;
        for(int i = 1;i <= n; ++i)
            for(int j = i + 1;j <= n; ++j)
            {
                if(i != pre[j] && j != pre[i] && a[i][j] != INF)
                    lsum = min(sum - maxd[i][j] + a[i][j],lsum);
            }
        if(lsum == sum) printf("Not Unique!\n");
        else printf("%d\n",sum);
    }
    return 0;
}