想象一下你是个城市基建规划者,地图上有 N 座城市,它们按以 1 到 N 的次序编号。
给你一些可连接的选项 conections,其中每个选项 conections[i] = [city1, city2, cost] 表示将城市 city1 和城市 city2 连接所要的成本。(连接是双向的,也就是说城市 city1 和城市 city2 相连也同样意味着城市 city2 和城市 city1 相连)。
返回使得每对城市间都存在将它们连接在一起的连通路径(可能长度为 1 的)最小成本。该最小成本应该是所用全部连接代价的综合。如果根据已知条件无法完成该项任务,则请你返回 -1。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/connecting-cities-with-minimum-cost
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
方向不敏感
每次选择最短的边
时间复杂度:O(eloge)
import java.util.*; public class Solution { public static int minimumCost(int n, int[][] connections) { Graph graph = new Graph(); Union union = new Union(n); for (int i = 0; i < connections.length; ++i) { graph.addEdge(connections[i][0], connections[i][1], connections[i][2]); } List<Edge> edges = graph.getEdges(); PriorityQueue<Edge> queue = new PriorityQueue<Edge>(new Comparator<Edge>() { @Override public int compare(Edge o1, Edge o2) { return o1.weight - o2.weight; } }); queue.addAll(edges); Set<Edge> resSet = new HashSet<Edge>(); while (!queue.isEmpty()) { Edge edge = queue.poll(); if (!union.inSameSet(edge.from.value, edge.to.value)) { resSet.add(edge); union.union(edge.from.value, edge.to.value); } } if (union.size() != 1) { return -1; } else { return resSet.stream().mapToInt(edge -> edge.weight).sum(); } } public static void main(String[] args) { int n = 3; int[][] arr = { {1, 2, 5}, {1, 3, 6}, {2, 3, 1} }; System.out.println(minimumCost(n, arr)); } } class Graph { private Map<Node, Map<Node, Edge>> edgeMap = new HashMap<>(); private Map<Integer, Node> nodes = new HashMap<>(); private List<Edge> edges = new ArrayList<>(); public List<Edge> getEdges() { return edges; } public Map<Integer, Node> getNodes() { return nodes; } /** * 如果边不存在,则创建边,同时保留最优边 * * @param from * @param to * @param weight * @return */ private Edge buildEdge(Node from, Node to, int weight) { Map<Node, Edge> fromMap = edgeMap.computeIfAbsent(from, k -> new HashMap<>()); Edge edge = fromMap.get(to); // 新边 if (edge == null) { edge = new Edge(from, to, weight); fromMap.put(to, edge); from.edges.add(edge); edges.add(edge); } else { // 留下最优边 if (edge.weight > weight) { edge.weight = weight; } } return edge; } /** * 如果不存在,则创建节点 * * @param index * @return */ private Node buildNode(int index) { Node node = nodes.get(index); if (node == null) { node = new Node(index); nodes.put(index, node); } return node; } /** * 添加边 * * @param fromIndex * @param toIndex * @param weight */ public void addEdge(int fromIndex, int toIndex, int weight) { buildEdge(buildNode(fromIndex), buildNode(toIndex), weight); } } class Edge { Node from; Node to; int weight; public Edge(Node from, Node to, int weight) { this.from = from; this.to = to; this.weight = weight; } } class Node { int value; int in; int out; List<Edge> edges; public Node(int value) { this.value = value; this.in = 0; this.out = 0; this.edges = new ArrayList<>(); } } class Union { private int[] parent; private int[] size; public Union(int n) { this.parent = new int[n + 1]; this.size = new int[n + 1]; for (int i = 1; i <= n; ++i) { parent[i] = i; size[i] = 1; } } public int find(int x) { int p = parent[x]; if (p == x) { return p; } p = find(p); parent[x] = p; return p; } public void union(int a, int b) { int p1 = find(a); int p2 = find(b); if (p1 == p2) { return; } if (size[p1] >= size[p2]) { parent[p2] = p1; size[p1] = size[p1] + size[p2]; size[p2] = 0; } else { parent[p1] = p2; size[p2] = size[p1] + size[p2]; size[p1] = 0; } } public boolean inSameSet(int a, int b) { return find(a) == find(b); } public int size() { int sum = 0; for (int i = 0; i < size.length; ++i) { if (size[i] > 0) { sum++; } } return sum; } }