社区讨论
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 条回复,欢迎继续交流。
正在加载回复...