UVA 10462 Is There A Second Way Left?(带重边次小生成树)

#include <bits/stdc++.h>
#define maxn 205
#define inf 0x3f3f3f3f
using namespace std;
struct Node{
	int x,y,w;
	bool operator < (const Node &a) const{
		return a.w > w;
	}
}Edge[maxn];
int pre[maxn], num;
int used[maxn];
int T,n,m;
int cnt;

void init(){
	for(int i=0;i<=n;i++) pre[i] = i;
}

void add(int u,int v,int w){
	Edge[num].x = u;
	Edge[num].y = v;
	Edge[num++].w = w;
}

int Find(int x){
	if(x != pre[x]) pre[x] = Find(pre[x]);
	return pre[x];
}

void Kruskal(){
	sort(Edge, Edge + num);
	for(int i=0;i<num;i++){
		int fx = Find(Edge[i].x);
		int fy = Find(Edge[i].y);
		if(fx != fy){
			pre[fx] = fy;
			used[cnt ++] = i;
		}
		if(cnt == n - 1) return;
	}
}

int main()
{
	int Case = 1;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);
		init();
		num = 0;
		for(int i=0;i<m;i++){
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			add(u, v, w);
			// add(v, u, w);
		}
		printf("Case #%d : ",Case++);
		cnt = 0;
		Kruskal();
		if(cnt != n - 1){
			puts("No way");
			continue;
		}
		if(m == n - 1){
			puts("No second way");
			continue;
		}
		int ans = inf;
		for(int i=0;i<cnt;i++){
			int sum = 0;
			int xx = 0;
			init();
			for(int j=0;j<num;j++){
				if(j == used[i]) continue;
				int fx = Find(Edge[j].x);
				int fy = Find(Edge[j].y);
				if(fx != fy){
					pre[fx] = fy;
					sum += Edge[j].w;
					xx ++;
				}
				if(xx == n - 1)break;
			}
			if(xx == n - 1) ans = min(ans, sum);
		}
		if(ans == inf)puts("No second way");
		else printf("%d\n", ans);
	}
	return 0;
}