http://poj.org/problem?id=167 9
问最小生成树是否唯一 其实就是问次小生成树是否等于最小生成树
思路：
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;
}
