判断一个无向连通图的MST是否唯一，其实本质上就是求是否存在次小树恰好等于MST。
16ms碾过~ 数据弱，不建议用来测试模版，据说有非SST做法，kuskal + LCA + O(E) ？求大神教学……
1
/*
2Problem: 1679 User: _mTy
3Memory: 760K Time: 16MS
4Language: G++ Result: Accepted
5
6Source Code
7*/
8
9#include<cstdio>
10#include<cstdlib>
11#include<cstring>
12#include<queue>
13#define N 101
14using namespace std;
15
16struct nod{
17 int u,max;
18};
19int g[N][N];
20int tree[N][N];
21int best[N][N];
22
23int prim(int n,int fa[]);
24
25int main(){
26 int t,n,m;
27 int i,j,u,v,w,t1,total;
28 int fa[N];
29 struct nod tmp,arr[N*N];
30 bool unique,visi[N];
31 scanf("%d",&t);
32 while(t--){
33 scanf("%d%d",&n,&m);
34 for(i=0;i<n;i++) for(j=0;j<n;j++) g[i][j]=0x7fffffff;
35 memset(tree,-1,sizeof(tree));
36 for(i=0;i<m;i++){
37 scanf("%d%d%d",&u,&v,&w);
38 g[u-1][v-1]=g[v-1][u-1]=w;
39 }
40 t1=prim(n,fa);
41 for(i=0;i<n;i++) tree[i][fa[i]]=tree[fa[i]][i]=g[i][fa[i]];
42
43 // bfs
44 total=0;
45 memset(best,-1,sizeof(best));
46 for(i=0;i<n;i++){
47 memset(visi,0,sizeof(visi));
48 arr[total].u=i; arr[total].max=-1;
49 queue<struct nod> _que; _que.push(arr[total]); ++total;
50 visi[i]=1;
51 while(!_que.empty()){
52 tmp = _que.front(); _que.pop();
53 for(v=0;v<n;v++)
54 if( !visi[v] && tree[tmp.u][v]!=-1 ){
55 visi[v]=1;
56 best[i][v]=
57 (tmp.max<tree[tmp.u][v])?tree[tmp.u][v]:tmp.max;
58 arr[total].max=best[i][v];
59 arr[total].u=v;
60 _que.push(arr[total]);
61 ++total;
62 }
63 }
64 }
65 unique = 1;
66 for(i=0;i<n;i++)
67 for(j=i+1;j<n;j++)
68 if( g[i][j]!=0x7fffffff && tree[i][j]==-1 )
69 if( t1 - best[i][j] + g[i][j] == t1 ) unique = 0;
70
71 if( unique ) printf("%d\n",t1);
72 else printf("Not Unique!\n");
73
74 }
75
76 return 0;
77}