Min Cost to Connect All Points
给一个数组, 里面是points, 求到每个点到所有点的最小cost.
这个是最小生成树算法, 我的用的k算法. 俺还优化了一下union find, 结果还是慢
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
class Solution { class Triple{ int from; int to; int weight; public Triple(int from, int to, int weight) { this.from = from; this.to = to; this.weight = weight; } } private static class DSU { int[] ranks; int[] parents; public DSU(int size) { this.ranks = new int[size]; Arrays.fill(ranks, 1); this.parents = new int[size]; for(int i = 0; i < size; i++){ this.parents[i]= i; } } int get(int v) { if (v == parents[v]) return v; return parents[v] = get(parents[v]); } boolean union(int a, int b) { a = get(a); b = get(b); if (a == b) return false; if (ranks[a] < ranks[b]) { int tmp = a; a = b; b = tmp; } parents[b] = a; if (ranks[a] == ranks[b]) ++ranks[a]; return true; } } public int minCostConnectPoints(int[][] points) { int n = points.length; PriorityQueue<Triple> g = new PriorityQueue<>((a, b) -> (a.weight - b.weight)); for(int i = 0; i < n; i++){ for(int j = i+1; j < n; j++) { g.add(new Triple(i, j, cost(points,i, j))); } } DSU dsu = new DSU(n); int res = 0; while (!g.isEmpty()) { Triple t = g.poll(); if (dsu.get(t.from) == dsu.get(t.to)) continue; dsu.union(t.from, t.to); res += t.weight; } return res; } public int cost (int[][] p, int i, int j) { return Math.abs(p[i][0] - p[j][0]) + Math.abs(p[i][1] - p[j][1]); } } |