题目链接：http://poj.org/problem?id=1679
题意：
给你一个图，问你这个图的最小生成树是否唯一。
题解：
求这个图的最小生成树和次小生成树。如果相等，则说明不唯一。
次小生成树（倍增算法）：
maxn[k][i]：表示从节点i向上走2^k步，这一段中边权的最大值。
枚举每一条不在MST中的边，求出这条边两端点之间在MST上路径上的最大边权mx。
次小生成树（非严格） = max(MST - mx + len)
AC Code:
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#define MAX_N 105
#define MAX_E 10005
#define MAX_K 20
#define INF 1000000000 using namespace std; struct E
{
int s;
int t;
int len;
E(int _s,int _t,int _len)
{
s=_s;
t=_t;
len=_len;
}
E(){}
friend bool operator < (const E &a,const E &b)
{
return a.len<b.len;
}
}; struct Edge
{
int dest;
int len;
Edge(int _dest,int _len)
{
dest=_dest;
len=_len;
}
Edge(){}
}; int n,m,t;
int fa[MAX_N];
int dep[MAX_N];
int par[MAX_K][MAX_N];
int maxn[MAX_K][MAX_N];
bool vis[MAX_E];
vector<E> e;
vector<Edge> edge[MAX_N]; void read()
{
cin>>n>>m;
e.clear();
for(int i=;i<=n;i++)
{
edge[i].clear();
}
int a,b,v;
for(int i=;i<=m;i++)
{
cin>>a>>b>>v;
e.push_back(E(a,b,v));
}
} void init_union_find()
{
for(int i=;i<=n;i++)
{
fa[i]=i;
}
} int find(int x)
{
return fa[x]==x ? x : fa[x]=find(fa[x]);
} void unite(int x,int y)
{
int px=find(x);
int py=find(y);
if(px==py) return;
fa[px]=py;
} bool same(int x,int y)
{
return find(x)==find(y);
} int kruskal()
{
init_union_find();
sort(e.begin(),e.end());
memset(vis,false,sizeof(vis));
int cnt=;
int res=;
for(int i=;i<e.size() && cnt<n-;i++)
{
E temp=e[i];
if(!same(temp.s,temp.t))
{
cnt++;
res+=temp.len;
vis[i]=true;
unite(temp.s,temp.t);
edge[temp.s].push_back(Edge(temp.t,temp.len));
edge[temp.t].push_back(Edge(temp.s,temp.len));
}
}
return cnt==n- ? res : -;
} void dfs(int now,int p,int d,int l)
{
dep[now]=d;
par[][now]=p;
maxn[][now]=l;
for(int i=;i<edge[now].size();i++)
{
Edge temp=edge[now][i];
if(temp.dest!=p) dfs(temp.dest,now,d+,temp.len);
}
} void init_lca()
{
dfs(,-,,-);
for(int k=;k+<MAX_K;k++)
{
for(int i=;i<=n;i++)
{
if(par[k][i]==-)
{
par[k+][i]=-;
maxn[k+][i]=-;
}
else
{
par[k+][i]=par[k][par[k][i]];
maxn[k+][i]=max(maxn[k][i],maxn[k][par[k][i]]);
}
}
}
} int cal_max(int a,int b)
{
if(dep[a]>dep[b]) swap(a,b);
int res=-;
for(int k=;k<=MAX_K && dep[a]!=dep[b];k++)
{
if(((dep[b]-dep[a])>>k)&)
{
res=max(res,maxn[k][b]);
b=par[k][b];
}
}
if(a==b) return res;
for(int k=MAX_K-;k>=;k--)
{
if(par[k][a]!=par[k][b])
{
res=max(res,maxn[k][a]);
res=max(res,maxn[k][b]);
a=par[k][a];
b=par[k][b];
}
}
return max(res,maxn[][a]);
} int sst(int mst)
{
if(mst==-) return -;
init_lca();
int ans=INF;
for(int i=;i<e.size();i++)
{
if(!vis[i])
{
E temp=e[i];
int mx=cal_max(temp.s,temp.t);
ans=min(ans,mst-mx+temp.len);
}
}
return ans==INF ? - : ans;
} void work()
{
int mst=kruskal();
if(mst==sst(mst)) cout<<"Not Unique!"<<endl;
else cout<<mst<<endl;
} int main()
{
cin>>t;
while(t--)
{
read();
work();
}
}