poj 1679 The Unique MST 夜

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

问最小生成树是否唯一    其实就是问次小生成树是否等于最小生成树

思路：

1  Kruskal 求最小生成树MIN 记录哪些边用了 哪些没有用 并建树

2  dfs 从每一点开始 求最小生成树上任意两点间的最长边

3 枚举没用过的边加入的情况 取(MIN+此边权-树中此两点间最长边权)  最小的那一个就是次小生成树

代码及其注释：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<map>
#include<queue>
#include<cmath>
#define LL long long

using namespace std;

const int N=105;

struct node
{
    struct tt *next;
}mem[N];
struct tt
{
    int j,k;
    struct tt *next;
};
struct ss
{
    bool used;
    int i,j,d;
}side[N*N];
int Mi_j[N][N];
int f[N];
void build(int i,int j,int d)//建树
{
    struct tt *t=new tt;
    t->j=j;
    t->k=d;
    t->next=mem[i].next;
    mem[i].next=t;
}
void Dele(int n)//删树
{
    for(int i=1;i<=n;++i)
    mem[i].next=NULL;
}
inline int findx(int x)//并查集
{
    if(f[x]!=x)
    f[x]=findx(f[x]);
    return f[x];
}
int Kruskal(int n,int m)//求最小生成树
{
    int sum=0;
    for(int i=1;i<=n;++i)
    f[i]=i;
    for(int l=0;l<m;++l)
    {
        int x=side[l].i;
        int y=side[l].j;
        if(findx(x)!=findx(y))
        {
            build(x,y,side[l].d);//建树
            build(y,x,side[l].d);
            f[findx(x)]=y;
            sum+=side[l].d;
            side[l].used=true;//标记是否用过
        }
    }
    return sum;
}
void dfs(int st,int x,int pre,int M)
{
    if(M!=0)
    Mi_j[st][x]=max(Mi_j[st][x],M);//求st到x最长边权
    struct tt *t=mem[x].next;
    while(t!=NULL)
    {
        if(t->j!=pre)
        {
            dfs(st,t->j,x,max(M,t->k));
        }
        t=t->next;
    }
}
int Fmtree(int n,int m,int MIN)
{
    int mtree=MIN+1;
    memset(Mi_j,0,sizeof(Mi_j));
    for(int i=1;i<=n;++i)
    dfs(i,i,0,0);//求树中任意两点间的最长边权
    for(int l=0;l<m;++l)
    {
        if(side[l].used==true)
        continue;
        int x=side[l].i;
        int y=side[l].j;
        mtree=min(mtree,MIN+side[l].d-Mi_j[x][y]);//枚举
    }
    return mtree;
}
int main()
{
    //freopen("data.txt","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        scanf("%d %d",&n,&m);
        for(int i=0;i<m;++i)
        {
            scanf("%d %d %d",&side[i].i,&side[i].j,&side[i].d);
            side[i].used=false;
        }
        int MIN=Kruskal(n,m);
        if(MIN==Fmtree(n,m,MIN))
        printf("Not Unique!\n");
        else
        printf("%d\n",MIN);
        Dele(n);
    }
    return 0;
}