城市建设-通过kruskal算法生成最小生成树 [Java][超详细注解]

解题思路:
首先是具有权值的图，然后还需要算出最小的造价。

那么可以很好想到需要生成一个最小生成树，当然这题的最小生成树比较特殊，

因为这里的道路权重如果小于0时，是可以赚钱的，所以遇到能赚钱的路，就必须建，不管是不是联通了。

生成最小生成树这道题用prim和kruskal算法都可以，反正只需要生成最小生成树就可以。

然后就是分情况

1. 不建桥 2. 建桥 

然后选择两种情况下造价较小的

注意事项:

认真读题，河道没有明确的连接关系，所以我们可以用 0 这个点作为他们的衔接点，

0 这个点没有权值，所以价格就是输入的那个码头的造价。如果觉得文字不好理解，可以直接看代码。

参考代码:

import java.util.*;

public class 城市建设_1437 {

    public static ArrayList<Edge> edges = new ArrayList<>();

    public static int[] vertices;

    public static int n;

    // 题目地址：https://www.dotcpp.com/oj/problem1437.html
    // 思路：使用kruskal算法生成最小生成树
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt() + 1;
        int m = scanner.nextInt();
        vertices = new int[n];
        // 输入桥梁
        for (int i = 0; i < m; i++) {
            int from = scanner.nextInt();
            int to = scanner.nextInt();
            int price = scanner.nextInt();
            edges.add(new Edge(from, to, price));
        }

        // 输入码头造价
        // 记录码头的数量
        int terNum = 0;
        for (int i = 1; i < n; i++) {
            int terPrice = scanner.nextInt();
            // 如果可以建码头，则码头也算是一条路，但是起点我们并不知道
            if (terPrice != -1) {
                edges.add(new Edge(i, 0, terPrice));
                terNum++;
            }
        }

        // 排序
        edges.sort(Comparator.comparingInt((o) -> o.price));

        // 不建码头的情况下
        int sum1 = kruskal(n, false);
        // 建码头的情况下
        int sum2 = kruskal(n + 1, true);
        // 选一个最小值
        System.out.println(Math.min(sum1, sum2));
    }

    public static int kruskal(int n, boolean isBuildTer) {
        // 初始化并查集
        initVertex();
        int sum = 0;
        for (Edge edge : edges) {
            // 如果他的 to==0 并且本次kruskal是不建桥的，就continue
            if (edge.to == 0 && !isBuildTer) continue;
            if (!isSame(edge)) {
                union(edge);
                sum += edge.price;
                n--;
            } else {
                if (edge.price < 0) {
                    // 如果这条路是可以赚钱的，则不管是否联通，都建造
                    sum += edge.price;
                }
            }
        }
        // 这里--n是因为n为了数据输入的时候方便操作在输入的时候+1了
        if (--n > 1) {
            return Integer.MAX_VALUE;
        } else {
            return sum;
        }
    }

    // 初始化并查集用的数组
    public static void initVertex() {
        for (int i = 0; i < n; i++) {
            vertices[i] = i;
        }
    }

    // Quick Union 实现形式 快速链接方式
    // 查找根节点
    public static int find(int v) {
        while (v != vertices[v]) {
            v = vertices[v];
        }
        return v;
    }

    // 判断是否相连
    public static boolean isSame(Edge edge) {
        return find(edge.from) == find(edge.to);
    }

    // 将edge的from和to连接
    public static void union(Edge edge) {
        vertices[find(edge.from)] = find(edge.to);
    }

    // 边对象
    private static class Edge {
        public int from;
        public int to;
        public int price;

        public Edge(int from, int to, int price) {
            this.from = from;
            this.to = to;
            this.price = price;
        }
    }
}