poj1679最小生成树是否唯一

http://www.cnblogs.com/kuangbin/p/3147329.html

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=110;

const int INF=0x3f3f3f3f;

bool vis[N];

int lowc[N],pre[N],Max[N][N];

bool used[N][N];

int Prim(int cost[][N],int n){

     int ans=0;

     memset(vis,0,sizeof(vis));

     memset(Max,0,sizeof(Max));

     memset(used,0,sizeof(used));

     vis[0]=1;

     pre[0]=-1;

     for(int i=1;i<n;++i) {

        lowc[i]=cost[0][i];

        pre[i]=0;

     }

     lowc[0]=0;

     for(int i=1;i<n;++i){

        int minc=INF;

        int p=-1;

        for(int j=0;j<n;++j) if(!vis[j]&&minc>lowc[j]) {

            minc=lowc[j];

            p=j;

        }

        if(minc==INF) return -1;

        ans+=minc;

        vis[p]=1;

        used[p][pre[p]]=used[pre[p]][p]=1;

        for(int j=0;j<n;++j){

            if(vis[j]) Max[j][p]=max(Max[j][pre[p]],lowc[p]);

            if(!vis[j]&&lowc[j]>cost[p][j]) {

                lowc[j]=cost[p][j];

                pre[j]=p;

            }

        }

     }

     return ans;

}

int ans;

int smst(int cost[][N],int n){

    int minn=INF;

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

        for(int j=i+1;j<n;++j)

        if(cost[i][j]!=INF&&!used[i][j])

        minn=min(minn,ans+cost[i][j]-Max[i][j]);

    if(minn==INF) return -1;

    return minn;

}

int cost[N][N];

int main(){

    int T,n,m;

    for(scanf("%d",&T);T--;){

        scanf("%d%d",&n,&m);

        int u,v,w;

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

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

            if(i==j) cost[i][j]=0;

        else cost[i][j]=INF;

        while(m--){

        scanf("%d%d%d",&u,&v,&w);

        --u;--v;

        cost[u][v]=cost[v][u]=w;

        }

        ans=Prim(cost,n);

        if(ans==-1) {

            puts("Not Unique");

            continue;

        }

        if(ans==smst(cost,n)) puts("Not Unique");

        else printf("%d\n",ans);

    }

}