研究了半天，最后还是暴搜解决的问题——题记

原题

给出一个无向连通图,问最小生成树是不是唯一的.
输入：第一行一个整数t（1 <= t <= 5), 表示测试数据的组数. 每组数据描述一个无向连通图,第一行是两个整数 n 和 m (1 <= n <= 100), 图中的点的个数和边数. 下面m行给出每条边(xi, yi, wi), 表示点xi和yi间有一条长为wi的边。
输出：对于每组输入,如果最小生成树是唯一的输出最小花费,否则输出’Not Unique!’.

思路

思考过程

对于这种的题，kruskal算法肯定是跑不了了······但是怎么去理解这个东西的数学本质就是一个有一定难度的问题了。就算是理解了，你还是很难避开这道题的一大天坑。
先说说我一开始的思路——以我个人的想法，如果我们在构树的时候能够随时考虑一下相等长度的边的话，即遇到某一长度的边，就试着将所有与其长度相等的边加入，看看是否有两条边能够连接同样的两个并查集就可以了。这样的思路实现起来其实并不难，因为并查集本身就是做这种事情的。
但是，这样真的能够解决所有的情况吗？

事实证明，不太靠谱······
一时间，我陷入了困境。所以到底是什么情况没有考虑到呢？
此时secretpal一句话道破了真相——原来边的输入顺序是不定的，所以在kruskal算法添加边的时候是存在一种在后期会被接入并查集的节点，而这种节点在前期可能被一条算法中没有用到的边连接到。为了方便大家理解，我可以试着用图片表示一下

如图所示，kruskal面对这种情况时就很尴尬了，事实上图4的情况中如果把先接上的那条边替换为被kurskal算法忽略（画叉）的那条边也是可以的，但是kruskal就是想不到这种情况。这样的情况也是多解的，但是我第一次的思路并没有考虑到这种情况。因此导致了大片WA。

最终思路

之后，在secretpal的提示下，我先构建完了一个可行的最小生成树，然后在我自行的思考下发现了一个规律——既然是树，那么就意味着我们可以通过唯一的一条路径连接两个节点，结合本题的数据，也证明了本题后期可以采用DFS这样简单粗暴的方法来寻找这条路径。如果我们加了任意一条边，就会形成环。在环中如果有一对等长的边，就说明这个图中的两条边可以互相替换。只要我们将没有用到的边的两端作为DFS的起点的终点，在搜索的时候检查路径上的边有无代价和没有被用到的边相等的边，就可以了。

大体思路下的一些代码小细节

数据

由于这道题中的数据肯定不止一组，为了节省一些空间，大家难免会将不少数组、数据变量等进行重复使用，这个时候每次循环间数据的重置就是我们要格外注意的。根据循环嵌套关系的不同，每种变量或数组都有它要更新的频率。这一点我们一定不能大意。评测机上开的新数组内数据是不固定的，这就要求我们在运算开始前将数组用memset或者手写for来清理好。像并查集表示、最小代价这样的数组每进行完一轮数据就要清空一次。存储边的结构体数组可以不清空，但是循环取用数据的时候一定不能多取，不然就会产生一些无中生有的边，一定概率会导致WA。像检查最小生成树是否构成连通图的CNT数组，一定要每增加一条边清空一次，不然100%的测试点都会WA。

输出提速

最后输出的时候，总有那么一些没用上的边是我们一眼就能看出来结论的。比如数据中出现的重边，就意味着我们可以直接下结论说最小生成树不唯一，如果存在起点终点都在同一个节点的边，那么这条边是可以不用考虑代替关系问题的。因为这样的边没有任何替代价值，并且这条边一旦加入，这个图就不是树了，而是环！多写几个if对于处理那些特别奇怪的数据提速有奇效，还减少了DFS的次数。

AC代码

/*由于博主日常生活学习时间紧迫，今天的代码注释实在没时间写了······
*/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
struct edge{
	int sa;
	int sb;
	int dis;
};
edge ed[5000];
bool used[5000];
int up[101];
int cnt[101];
int smalltree[101][101];
int maxcnt;
int spd;
bool uproute[101];
int t,n,m;//point and edge
bool insteadable ;
bool pd(edge a,edge b){
	return a.dis<b.dis;
}
void dfs(int now,int to,int fr,int l,bool found){
	if(now==to){
		insteadable = found;
		return;
	}
	for(int a = 1;a<=100;a++){
		if(smalltree[now][a]==l&&a!=fr&&a!=now){
			dfs(a,to,now,l,true);
		}
		else if(a!=fr&&smalltree[now][a]!=0x3f3f3f3f&&a!=now){
			dfs(a,to,now,l,found);
		}
	}
}
int fd(int now){
	if(up[now]==now){
		return now;
	}
	up[now]=fd(up[now]);
	return up[now];
}

//---------------------------------------------------------------------------------------
int main(){
	scanf("%d",&t);
	for(int a = 0;a<t;a++){
		memset(smalltree,0x3f3f3f3f,sizeof smalltree);
		//重新构建并查集 
		spd = 0;
		memset(used,0,sizeof used); 
		for(int b = 0;b<101;b++){
			up[b]=b;
		}
		scanf("%d%d",&n,&m);
		spd = 0;
		for(int b = 0;b<m;b++){
			scanf("%d%d%d",&ed[b].sa,&ed[b].sb,&ed[b].dis);
		}
		sort(ed,ed+m,pd);//sort finished
		for(int b = 0;b<m;b++){//加上第b条边 
		memset(cnt,0,sizeof cnt);
		maxcnt = 0;
		if(up[ed[b].sa]!=up[ed[b].sb]){
		up[fd(ed[b].sa)]=fd(ed[b].sb);
		smalltree[ed[b].sa][ed[b].sb]=ed[b].dis;
		smalltree[ed[b].sb][ed[b].sa]=ed[b].dis;
		spd+=ed[b].dis;
		used[b]=true;
		for(int c = 1;c<=n;c++){
			fd(c);
		} 
		for(int c = 1;c<=n;c++){
			cnt[up[c]]++;
			maxcnt=max(maxcnt,cnt[up[c]]);
		}
		if(maxcnt == n){ 
			break;
		}
		}
	}//已构建最小生成树，准备尝试替换 
	bool out = false;
	for(int c = 0;c<m;c++){
		insteadable = false;
		if(!used[c]){
			if(smalltree[ed[c].sa][ed[c].sb]==ed[c].dis){
				printf("Not Unique!\n");
				out = true;
				break;
			}
			else if(smalltree[ed[c].sa][ed[c].sb]!=ed[c].dis&&smalltree[ed[c].sa][ed[c].sb]!=0x3f3f3f3f||ed[c].sa==ed[c].sb){
				;
			}
			else{
			dfs(ed[c].sa,ed[c].sb,ed[c].sa,ed[c].dis,false);
			if(insteadable){
				printf("Not Unique!\n");
				out = true;
				break;
			}
			}
		}
	}
	if(!out){
		printf("%d\n",spd);
	}
	}
	return 0;
}