题意：
给一个n个节点，m条边的无向图，问你该图的最小生成树是否唯一？如果唯一输出树的权值，否则输出“Not unique!”
题解：
次小生成树：
一个图的次小生成树(权值<=最小生成树的权值,可能等于最小生成树的权值)肯定至少有一条边与最小生成树的一条边不同.所以我们可以枚举最小生成树上的边,然后依次用m-1条边的无向图来重新生成最小生成树,求出新生成的最小生成树中的权值最小值即为次小生成树的权值。
求出次小生成树的权值，如果和最小生成树的权值一样，说明最小生成树不唯一！
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<string>
#include<cstring>
#include<vector>
#include<functional>
#include<utility>
#include<set>
#include<map>
#include<cmath>
#include<cctype>using namespace std;
const int maxn=110;struct edge
{int u,v,cost;int id;edge(int u,int v,int d,int id):u(u),v(v),cost(d),id(id) {}bool operator<(const edge& a)const{return cost<a.cost;}
};vector<edge>es;
vector<int>E;
int pa[maxn];
int n;int findset(int x)
{return pa[x]<0?x:pa[x]=findset(pa[x]);
}int kk(int id)
{int cnt=0;int ans=0;memset(pa,-1,sizeof(pa));sort(es.begin(),es.end());for(int i=0; i<es.size(); i++){ if(es[i].id==id)continue;//id边被删除int u=es[i].u,v=es[i].v;if(findset(u)!=findset(v)){ans+=es[i].cost;if(id==-1)//最小生成树时，存边idE.push_back(es[i].id);pa[findset(u)]=findset(v);if(++cnt>=n-1)break;}}return cnt>=n-1? ans:-1;
}int main()
{int t;cin>>t;while(t--){ es.clear();E.clear();int m;cin>>n>>m;for(int i=0;i<m;i++){int u,v,d;cin>>u>>v>>d;es.push_back(edge(u,v,d,i));}int ans1=kk(-1);//最小int ans2;for(int i=0;i<E.size();i++){ans2=kk(E[i]);if(ans2==-1)continue;//删除一个后，不连通，不存在最小生成树。if(ans2==ans1)break;}if(ans1==ans2)puts("Not Unique!");else cout<<ans1<<endl;}
}