POJ 1679 The Unique MST

判断次小生成树是否和最小生成树相等

Description

Input

Output

Sample Input

2
3 3
1 2 1
2 3 2
3 1 3
4 4
1 2 2
2 3 2
3 4 2
4 1 2

Sample Output

3
Not Unique!

Source

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn=111,INF=0x3f3f3f3f;

int G[maxn][maxn],maxd[maxn][maxn],fa[maxn],n,m,dist[maxn],vis[maxn];

int prim()
{
    int ret=0;
    for(int i=1;i<=n;i++) fa[i]=i;
    memset(dist,63,sizeof(dist));
    memset(vis,0,sizeof(vis));
    memset(maxd,0,sizeof(maxd));

    dist[1]=0;
    int dd,mark;
    for(int k=0;k<n;k++)
    {
        dd=INF,mark=-1;
        for(int j=1;j<=n;j++)
        {
            if(vis[j]==0&&dist[j]<dd)
            {
                dd=dist[j],mark=j;
            }
        }
        if(mark==-1) return INF;

        vis[mark]=1;ret+=dd;


        for(int i=1;i<=n;i++)
        {
            if(vis[i])
            {
                maxd[i][mark]=maxd[mark][i]=max(dd,maxd[fa[mark]][i]);
            }
        }

        for(int j=1;j<=n;j++)
        {
            if(vis[j]==0&&G[mark][j]<dist[j])
            {
                dist[j]=G[mark][j];
                fa[j]=mark;
            }
        }
    }
    return ret;
}

int main()
{
    int t;
    scanf("%d",&t);
while(t--)
{
    scanf("%d%d",&n,&m);
    memset(G,63,sizeof(G));

    for(int i=0;i<m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        G[a][b]=G[b][a]=c;
    }

    int mst1=prim();

    int ct=INF;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j) continue;
            if(G[i][j]&&i!=fa[j]&&j!=fa[i])
            {
                ct=min(G[i][j]-maxd[i][j],ct);
            }
        }
    }
    if(ct==0) puts("Not Unique!");
    else printf("%d\n",mst1);
}
    return 0;
}

POJ 1679 The Unique MST

原文：http://blog.csdn.net/u012797220/article/details/19622999