N \le 1000,M \le 100000N≤1000,M≤100000
x \le N,y \le N,t \le 100000x≤N,y≤N,t≤100000
题解. 既可以用并查集查询合并次数, 也可以用最小生成树做.
基于本热对最小生成树比较熟悉, 那就用最小生成树啦~
稍微注意一下 ans=max(ans,e[i].t) 即可.
- #include<cstdio>
- #include<iostream>
- #include<cmath>
- #include<cstdlib>
- #include<cstring>
- #include<algorithm>
- typedef long long ll;
- using namespace std;
- int n,m,fa[1005];
- struct node{
- int x,y,t;
- }e[100005];
- bool cmp(node aa,node bb){
- return aa.t<bb.t;
- }
- int find(int x){
- if(x!=fa[x])
- fa[x]=find(fa[x]);
- return fa[x];
- }
- int Yao_Chen_Lai_Le(int nb){
- int tot=0,ans=0;
- // for(int i=1;i<=n;i++) fa[i]=i;
- for(int i=1;i<=m;i++){
- int uu=find(e[i].x);
- int vv=find(e[i].y);
- if(uu==vv) continue;
- ans=max(ans,e[i].t);
- fa[uu]=vv; tot++;
- if(tot==(n-1)) break;
- }
- if(tot==(n-1)) return ans;
- else return -1;
- }
- int main(){
- freopen("1111.in","r",stdin);
- freopen("1111.out","w",stdout);
- scanf("%d %d",&n,&m);
- for(int i=1;i<=m;i++)
- scanf("%d %d %d",&e[i].x,&e[i].y,&e[i].t);
- sort(e+1,e+m+1,cmp);
- for(int i=1;i<=n;i++) fa[i]=i;
- cout<<Yao_Chen_Lai_Le(666);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3192300.html