ACM: meixiuxiu学图论-并查集-最小生成树-解题报告

/*

最小生成树，最小环的最大权值按照排序后去构建最小生成树就可以了，注意遇到的第一个根相同的点就记录权值，跳出，生成的环就是最小权值环。

*/

//AC代码：

#include"iostream"

#include"cstdio"

#include"cstring"

#include"cmath"

#include"algorithm"

using namespace std;

const int MX=2222222;

int pe[MX];

struct node {

	int s,e,q;

} side[MX];

int find(int x) {

	return pe[x]==x?x:(pe[x]=find(pe[x]));

}

bool cmp(node a,node b) {	//按照权值升序排序

	return a.q<b.q;

}

int main() {

	int T,n,m,maxx,flag;

	scanf("%d",&T);

	while(T--) {

		scanf("%d%d",&n,&m);

		for(int i=0; i<=n; i++)pe[i]=i;

		for(int i=0; i<m; i++) {

			scanf("%d%d%d",&side[i].s,&side[i].e,&side[i].q);

		}

		maxx=-100;

		flag=0;

		sort(side,side+m,cmp);

		for(int i=0; i<m; i++) {

			int rt1=find(side[i].s),rt2=find(side[i].e);

			if(rt1!=rt2) {

				pe[rt2]=rt1;		//先构造最小生成树

				maxx=max(maxx,side[i].q);

			}

			if(rt1==rt2) {

				maxx=max(maxx,side[i].q);//找到两个根相同的节点，连起来就构成了最小环

				flag=1;

				break;

			}

		}

		if(!flag)printf("No solution!\n");

		else printf("%d\n",maxx);

	}

	return 0;

}

/*  样例：

2

3 2

1 2 3

2 3 4

5 6

1 2 1

2 3 2

1 3 4

3 4 5

4 5 2

5 3 8

*/