题解 P1111 【修复公路】

zhangxujing · 2019-10-31 16:31:21 · 题解

include <bits/stdc++.h>

using namespace std;

struct bcj { int b,e,t; }a[100005]; int n,m,fa[1005]; bool cmp(bcj x,bcj y) { return x.t<y.t; } void init() { for(int i=1;i<=n;i++) fa[i]=i; } int findf(int x) { if(fa[x]==x) return x; return fa[x]=findf(fa[x]); } void Union(int x,int y) { fa[findf(x)]=findf(y); } bool isf(int x,int y) { return findf(x)==findf(y); }

int main() { ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=m;i++) cin>>a[i].b>>a[i].e>>a[i].t; sort(a+1,a+m+1,cmp); init(); //for(int i=1;i<=m;i++) cout<<a[i].t<<endl; for(int i=1;i<=m;i++) { if(!isf(a[i].b,a[i].e)) Union(a[i].b,a[i].e); bool flag=0; int cnt=0; for(int j=1;j<=n;j++) { if(fa[j]==j) cnt++; if(cnt==2) { flag=1; break; } } if(!flag) { cout<<a[i].t; return 0; } } cout<<-1; return 0; }