19914 最小生成树2
⭐️难度：中等
🌟考点：最小生成树
📖
📚
import java.util.*;public class Main {static class Edge{int u,v,w;Edge(int u,int v,int w){this.u = u;this.v = v;this.w = w;}}static ArrayList<Edge> g = new ArrayList<>(); // 存边static int n;static int m;static class UnionSet{ // 并查集int[] f,sz;UnionSet(int n){f = new int[n+1];sz = new int[n+1];for (int i = 1; i <= n; i++) {f[i] = i;sz[i] = i;}}int find(int x){return f[x] == x ? x : (f[x] = find(f[x]));}void union(int x,int y){int fx = find(x);int fy = find(y);if(sz[fx] < sz[fy]){f[fx] = fy;sz[fy] += sz[fx];}else{f[fy] = fx;sz[fx] += sz[fy];}}}static boolean kruskal(){g.sort(Comparator.comparingInt(e ->e.w));UnionSet us = new UnionSet((n));int cnt = 0;int ans = 0; // 边权for(Edge e : g){if(us.find(e.u) == us.find(e.v)) continue;us.union(e.u,e.v);ans += e.w;if(++cnt == n-1){System.out.println(ans);return true;}}return false;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();m = sc.nextInt();for (int i = 0; i < m; i++) {g.add(new Edge(sc.nextInt(), sc.nextInt(),sc.nextInt()));}if(!kruskal()){System.out.println("impossible");}}
}
🍎笔记
