$P1547 Out of Hay$

佚名 6年前 (2019-04-20) 随笔 597人围观抢沙发百度已收录

$problem$
$kruskal$模板题$qwq$
$(2 <= N <= 2,000)$
所以边数是 $2000^2\ /2$ 不是 $2^{18}$

#include <bits/stdc++.h>
using namespace std;
typedef long long LL ;
LL n,m,p;
LL s=-0x7f7f7f7f;
LL cnt=0;
LL f[1<<18] ;
struct node{
    int a,b,x;
}a[1<<18];
bool cmp (node x, node y) {
    return x.x<y.x;
}
inline int get(int x) {
    if (f[x]!=x) f[x]=get(f[x]);
    return f[x];
}
inline void kruskal() {
    register int cnt=0;
    register int x,y;
    for(register int i=1;i<=n;i++) f[i]=i;
    for(register int i=1;i<=m;i++) {
        x = get(a[i].a) ; y = get(a[i].b) ;
        if(x == y) continue;
        s= max(x,a[i].x);
        f[x]=y; cnt++;
        if (cnt == n-1) break;
    }
    if (cnt<n-1) cout << -1 << endl ;
    else cout << s << endl ;
} 
signed main() {
    ios::sync_with_stdio(false);
    cin >> n >> m ;
    for(register int i=1;i<=m;i++) cin >> a[i].a >> a[i].b >> a[i].x;
    sort(a+1,a+m+1,cmp) ;
    kruskal();
    return 0;
}