The Unique MST-POJ1679(次小生成树)

http://poj.org/problem?id=1679

次小生成树

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>

using namespace std;
#define N 200
#define INF 0xfffffff

int G[N][N],vis[N],dis[N],n,m,pre[N];
int Max[N][N],use[N][N];

void Inn()
{
    int i,j;
    for(i=0;i<=N;i++)
    {
        dis[i]=0;
        for(j=0;j<=N;j++)
        {
            if(i==j)
                G[i][j]=0;
            else
                G[i][j]=INF;
        }
    }
    memset(vis,0,sizeof(vis));
    memset(use,0,sizeof(use));
    memset(Max,0,sizeof(Max));
    memset(pre,0,sizeof(pre));
}

int prime(int s)
{
    int i,j,ans=0;
    for(i=1;i<=n;i++)
    {
        dis[i]=G[s][i];
        pre[i]=s;
    }
    vis[s]=1;
    for(i=1;i<n;i++)
    {
        int Min=INF,dist=1;
        for(j=1;j<=n;j++)
        {
            if(!vis[j] && dis[j]<Min)
            {
                Min=dis[j];
                dist=j;
            }
        }
        ans+=Min;
        vis[dist]=1;
        use[dist][pre[dist]]=use[pre[dist]][dist]=1;
        for(j=1;j<=n;j++)
        {
            if(vis[j] && j!=dist)
                Max[dist][j]=Max[j][dist]=max(Max[dist][j],dis[dist]);
            if(!vis[j] && dis[j]>G[dist][j])
            {
                dis[j]=G[dist][j];
                pre[j]=dist;
            }
        }
    }
    return ans;
}

int SMST(int a)
{
    int minn=INF,i,j;
    for(i=1;i<=n;i++)
    {
        for(j=i+1;j<=n;j++)
        {
            if(!use[i][j] && G[i][j]!=INF)
                minn=min(minn,a-Max[i][j]+G[i][j]);
        }
    }
    return minn;
}

int main()
{
    int T,i,a,b,c;
    scanf("%d",&T);
    while(T--)
    {
        Inn();
        scanf("%d %d",&n,&m);
        for(i=0;i<m;i++)
        {
            scanf("%d %d %d",&a,&b,&c);
            G[a][b]=G[b][a]=c;
        }
        int n1=prime(1);
        int n2=SMST(n1);
        if(n1==n2)
            printf("Not Unique!
");
        else
            printf("%d
",n1);
    }
    return 0;
}