2 条题解
-
1
#include<bits/stdc++.h> using namespace std; void read(int &h){ char o; int x=0,y=1; o=getchar_unlocked(); while(!(o<='9'&&o>='0')){ if(o=='-'){ y=-1; } o=getchar_unlocked(); } while(o<='9'&&o>='0'){ x*=10; x+=o-'0'; o=getchar_unlocked(); } h=x*y; return ; } const int N=1e5+10; struct road{ int x,y,t; }a[N]; int n,m,tree[N],u,v,o; bool cmd(road a,road b){ return a.t<b.t; } int find_root(int x){ if(tree[x]==x){ return x; } return tree[x]=find_root(tree[x]); } void start(){ o=n; for(int i=1;i<=n;i++){ tree[i]=i; } return ; } int main(){ ios::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr); read(n);read(m); start(); for(int i=1;i<=m;i++){ read(a[i].x);read(a[i].y);read(a[i].t); } sort(a+1,a+m+1,cmd); for(int i=1;i<=m;i++){ u=find_root(a[i].x); v=find_root(a[i].y); if(u!=v){ tree[u]=v; o--; } if(o==1){ cout<<a[i].t<<" "; return 0; } } cout<<-1; return 0; } -
-1
#include<bits/stdc++.h>//2 using namespace std; const int N=100010; int f[N]; struct Node{ int x,y,t; }a[N]; bool cmd(Node a,Node b) { return a.t<b.t; } int find(int x) { if(f[x]!=x) f[x]=find(f[x]); return f[x]; } int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) f[i]=i; for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].t); sort(a+1,a+m+1,cmd); int cnt=n-1; for(int i=1;i<=m;i++) { int fa=find(a[i].x); int fb=find(a[i].y); if(fa==fb) continue; f[fa]=fb; cnt--; if(cnt==0) { printf("%d",a[i].t); return 0; } } printf("-1"); return 0; }
- 1
信息
- ID
- 5169
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 5
- 标签
- 递交数
- 43
- 已通过
- 17
- 上传者