记录编号	559600	评测结果	AAAAAAAAAA
题目名称	[福州培训2010] 修复公路	最终得分	100
用户昵称	tat	是否通过	通过
代码语言	C++	运行时间	0.534 s
提交时间	2021-03-19 21:05:51	内存使用	2.07 MiB

#include <bits/stdc++.h>
using namespace std;
//加权并查集，每次添加某个边的时候查看size[f(x)]是否等于n 
int f[1001],size[1001],n,m;
struct edge{
	int x,y,t;
	bool operator < (const edge &tmp)const{
		return this->t>tmp.t;
	}
};
priority_queue<edge> ed;
int get(int x){
	if(f[x]==x)return x;
	int root=get(f[x]);
	return root;
}
int main(int argc, char** argv) {
	freopen("roada.in","r",stdin);
	freopen("roada.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		f[i]=i;
		size[i]=1;
	}
	for(int i=1;i<=m;i++){
		edge input;
		int x,y,t;
		cin>>x>>y>>t;
		input.x=x;input.y=y;input.t=t;
		ed.push(input);
	} 
	while(!ed.empty()){
		edge tmp=ed.top();
		ed.pop();
		int x=get(tmp.x);
		int y=get(tmp.y);
		int t=tmp.t;
		if(f[x]!=f[y]){
			f[x]=y;
			size[y]+=size[x];
			if(size[y]==n){
				cout<<tmp.t<<endl;
				return 0;
			}
		}
	}
	cout<<-1;
	return 0;
}