社区讨论

10分求调

P1111修复公路参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lzrs1ao3
此快照首次捕获于
2024/08/13 10:01
2 年前
此快照最后确认于
2024/08/13 11:50
2 年前
查看原帖
CPP
#include <iostream>
#include <algorithm>
using namespace std;
int fa[1000000];
struct node
{
	int x,y,t;
}p[1000000];
bool cmp(node a,node b) {return a.t<b.t;}
int finnd(int x) { return fa[x] == x ? x : fa[x] = finnd(fa[x]); }
void merge(int x, int y) { if(finnd(x)!=finnd(y))fa[finnd(x)] = finnd(y); }
int main() {
    int n, m;
    cin >> n >> m;
    int mm=m;
    for(int i=1;i<=n;i++){fa[i] = i;}
    for(int i=1;i<=m;i++) cin >> p[i].x >> p[i].y >> p[i].t;
	sort(p+1,p+mm+1,cmp);
    for(int i=1;i<=mm;i++)
    {
    	merge(p[i].x,p[i].y),n--;
    	if(n==1) 
		{
			cout<<p[i].t;
			return 0;
		}
  	}
  	cout<<-1;
  	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...