這是一個次小生成樹的題目，我們知道要求最小生成樹的方法，次小生成樹在最小生成樹的基礎上運算就可以了，這裡采用最簡單的方法就是去掉最小生成樹集合當中的每一條邊再做kruskal,每次kruskla的時間復雜度有mlogm+m,進行最小生成樹中邊集的枚舉復雜度為(n-1)*(m*logm+m),這題還是做到的，還有一種更好的方法，只要做一次kruskal就好了，實現起來有點復雜。
先貼本題的代碼：
[cpp]
#include<iostream>
#include<algorithm>
#define maxn 105
#define maxe 5050
using namespace std;
struct Edge
{
int a,b,w,flag;
} e[maxe];
int n,m,c;
int f[maxn],used[maxn];
void Set()
{
for(int i=1; i<=n; i++){
f[i]=i;
}
}
int Find(int x)
{
if( x!=f[x])
f[x]=Find(f[x]);
return f[x];
}
bool cmp(Edge a,Edge b)
{
return a.w<b.w;
}
int Kruskal()
{
int i,x,y,ret;
ret=0; c=0;
Set();
for( i=0; i<m&&c<n-1; i++){
x=Find(e[i].a);
y=Find(e[i].b);
if( x==y) continue;
f[x]=y;
ret+=e[i].w;
used[c++]=i;
}
return (c<n-1? 0:ret);
}
int SecKruskal()
{
int i,x,y,ret,count;
ret=0; count=0;
Set();
for( i=0; i<m&&count<n-1; i++){
x=Find(e[i].a);
y=Find(e[i].b);
if( x==y|| e[i].flag) continue;
f[x]=f[y];
ret+=e[i].w;
count++;
}
return ( count<n-1? 0:ret);
}
int main()
{
int t,mst,smst,pt,i;
scanf("%d",&t);
while( t--){
scanf("%d%d",&n,&m);
memset(e,0,sizeof(e));
memset(used,0,sizeof(used));
memset(f,0,sizeof(f));
for( i=0; i<m; i++)
scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].w);
sort(e,e+m,cmp); //按邊值大小排序
mst=Kruskal(); //第一次kruskal求最小生成樹 mst
pt=0; //最小生成樹不同至少要有一條邊不同。
for( i=0; i<c; i++){
e[used[i]].flag=1;
smst=SecKruskal();
e[used[i]].flag=0;
if( smst==mst&&smst!=0){ //如果最小樹不是唯一的。
pt=1;
break;
}
}
if( pt)
printf("Not Unique!\n");
else
printf("%d\n",mst);
}
return 0;
}
