POJ 1679 次小生成树

//求次小生成树是否等于最小生成树。
//次小生成树最多有一条边与最小生成树不同，求出最小生成树后，枚举不在最小生成树中的边u-v，
//加入这条边会形成环，因此再去掉最小生成树中u-v路径中的权值最大的边。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int t,n,m,mp[110][110],vis[110],maxl[110][110],dis[110],pre[110],used[110][110];
int Spfa(){
    memset(maxl,0,sizeof(maxl));
    memset(used,0,sizeof(used));
    for(int i=1;i<=n;i++){
        dis[i]=mp[1][i];
        vis[i]=0;pre[i]=1;
    }
    vis[1]=1;
    int ans=0;
    for(int i=1;i<n;i++){
        int minl=inf,sta=-1;
        for(int j=1;j<=n;j++){
            if(!vis[j]&&dis[j]<minl){
                minl=dis[j];
                sta=j;
            }
        }
        if(sta==-1) return -1;
        vis[sta]=1;
        used[sta][pre[sta]]=used[pre[sta]][sta]=1;
        ans+=minl;
        for(int j=1;j<=n;j++){
            if(vis[j])
                maxl[sta][j]=maxl[j][sta]=max(maxl[pre[sta]][j],dis[sta]);
            else if(dis[j]>mp[sta][j]){
                dis[j]=mp[sta][j];
                pre[j]=sta;
            }
        }
    }
    return ans;
}
int Smst(int ans){
    int tmp=inf;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(used[i][j]||mp[i][j]==inf) continue;
            tmp=min(tmp,ans+mp[i][j]-maxl[i][j]);
        }
    }
    if(tmp==inf) return -1;
    return tmp;
}
int main()
{
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        memset(mp,inf,sizeof(mp));
        for(int i=1;i<+n;i++) mp[i][i]=0;
        int a,b,c;
        for(int i=0;i<m;i++){
            scanf("%d%d%d",&a,&b,&c);
            mp[a][b]=mp[b][a]=min(mp[a][b],c);
        }
        int ans=Spfa();
        if(ans==-1){
            printf("Not Unique!\n");continue;
        }
        int tmp=Smst(ans);
        if(tmp==ans) printf("Not Unique!\n");
        else printf("%d\n",ans);
    }
    return 0;
}