Principle:

• Enumerate every edge not on the minimum spanning tree as the edge on the minimum spanning tree, then form a ring, remove the longest path on the ring (except the edge enumerated), update the weight sum of the sub small spanning tree,
• Finally, compared with the weight and sum of the minimum spanning tree, the same means that life exists.
• In fact, if the sub small spanning tree exists, there must be an edge in the minimum spanning tree with the same weight as the edge not in the minimum spanning tree in the graph.
• Enumerate every edge not on the minimum spanning tree by enumerating points

1. pre[maxn]: record the previous point of each point
2. maxdist[maxn][maxn]: update the maximum edge between 2 points in the minimum spanning tree.
3. use[maxn][maxn]: mark whether the edge is in the minimum spanning tree.
4. The principle of maximum edge update between 2 points of minimum spanning tree: picture
   if (vis[j]) maxdist[j][point] = maxdist[point][j] =max(maxdist[j][pre[point]],dist[point]);

prim+ example POj 1679

#include <iostream>
#include <iostream>
#include <string.h>

using namespace std;
const int maxn = 1e3+5;
const int INF = 0x3f3f3f3f;

bool vis[maxn];
int dist[maxn];
int e[maxn][maxn];
int n,m;
int sum;
bool use[maxn][maxn];
int maxdist[maxn][maxn];
int pre[maxn];

int prim() {
	sum = 0;
	memset(vis,0,sizeof vis);
	memset(use,0,sizeof use);
	memset(maxdist,0,sizeof maxdist);
	vis[1] = 1; //Add point 1 to the minimum spanning tree
	for (int i=2; i<=n; i++) {
		dist[i] = e[1][i];
		pre[i] = 1;
	}
	pre[1] = 0;

	for (int i=1; i<n; i++) {
		int minn = INF;
		int point = INF;
		for (int j=1; j<=n; j++) {
			if (!vis[j] && dist[j]<minn) {
				point = j;
				minn = dist[j];
			}
		}
		vis[point] = 1;
		sum += minn;
		use[point][pre[point]] = use[pre[point]][point] = 1; //Mark point in tree

		for (int j=1; j<=n; j++) { //Update the distance from each point to the tree
			if (vis[j]) 
				maxdist[j][point] = maxdist[point][j] =max(maxdist[j][pre[point]],dist[point]);
			if (!vis[j] && e[point][j] < dist[j]) {
				dist[j] = e[point][j];
				pre[j] = point; //Now that you have updated the path, also update the previous point that this point points to
			}
		}
	}
	return sum;
}
int superprim() {
	int ans = INF;
	for (int i=1; i<=n; i++) { //Enumerate all
		for (int j=i+1; j<=n; j++) {
			if (!use[i][j] && e[i][j]!=INF) 
				ans = min(sum+e[i][j]-maxdist[i][j],ans);
		}
	}
	return ans;
}

int main() {
//	freopen("a.txt","r",stdin);
	int times; cin >> times;
	while (times--) {
		cin >> n >> m;
		memset(e,0x3f,sizeof e);
		for (int i=1; i<=m; i++) {
			int u,v,w;
			cin >> u >> v >> w;
			e[u][v] = e[v][u] = min(e[u][v],w);
		}
		if(prim()==superprim())///Determine whether the results of the sub small spanning tree and the minimum spanning tree are the same
            printf("Not Unique!\n");
        else
            printf("%d\n",sum);
	}
	return 0;
}