#include<bits/stdc++.h> using namespace std; const int N = 1e5 + 10, M = 2e5 + 10, INF = 0x3f3f3f3f; int n, m, f[N]; struct edge{ int f, t, l; edge(){} edge(int ff, int tt, int ll) { f = ff, t = tt, l = ll; } friend bool operator <(edge a, edge b) { return a.l < b.l; } }e[M]; int get(int x) { if(x != f[x]) f[x] = get(f[x]); return f[x]; } int kruskal() { int res = 0, cnt = 0; sort(e, e + m); for(int i = 0; i < m; i ++ ) { int ff = get(e[i].f), tt = get(e[i].t), ll = e[i].l; if(ff != tt) { cnt ++ ; res += ll; f[ff] = tt; } } if(cnt == n - 1) return res; return INF; } int main() { cin >> n >> m; for(int i = 0; i < m; i ++ ) { int ff, tt, ll; cin >> ff >> tt >> ll; e[i] = edge(ff, tt, ll); } for(int i = 1; i <= n; i ++ ) f[i] = i; int t = kruskal(); if(t == INF) puts("impossible"); else cout << t << endl; return 0; }
标签:ll,int,kruskal,edge,ff,tt From: https://www.cnblogs.com/leyuo/p/16646507.html