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=;i<=N;i++)

    {

        dis[i]=;

        for(j=;j<=N;j++)

        {

            if(i==j)

                G[i][j]=;

            else

                G[i][j]=INF;

        }

    }

    memset(vis,,sizeof(vis));

    memset(use,,sizeof(use));

    memset(Max,,sizeof(Max));

    memset(pre,,sizeof(pre));

}

int prime(int s)

{

    int i,j,ans=;

    for(i=;i<=n;i++)

    {

        dis[i]=G[s][i];

        pre[i]=s;

    }

    vis[s]=;

    for(i=;i<n;i++)

    {

        int Min=INF,dist=;

        for(j=;j<=n;j++)

        {

            if(!vis[j] && dis[j]<Min)

            {

                Min=dis[j];

                dist=j;

            }

        }

        ans+=Min;

        vis[dist]=;

        use[dist][pre[dist]]=use[pre[dist]][dist]=;

        for(j=;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=;i<=n;i++)

    {

        for(j=i+;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=;i<m;i++)

        {

            scanf("%d %d %d",&a,&b,&c);

            G[a][b]=G[b][a]=c;

        }

        int n1=prime();

        int n2=SMST(n1);

        if(n1==n2)

            printf("Not Unique!\n");

        else

            printf("%d\n",n1);

    }

    return ;

}