import java.util.Arrays; import java.util.Scanner; class Edge implements Comparable<Edge> { int x; int y; int length; Edge(int x, int y, int length) { this.x = x; this.y = y; this.length = length; } public int compareTo(Edge e) { if (length > e.length) return 1; else if (length < e.length) return -1; return 0; } } public class lab1160 { public static int find(int[] p, int x) { if (p[x] == x) return x; else return p[x] = find(p, p[x]); } public static void main(String[] args) { Scanner scanner = new Scanner( System.in); int n = scanner.nextInt(); int m = scanner.nextInt(); Edge[] edges = new Edge[m]; int sum = 0; int totalLength = 0; int[] p = new int[n]; int[] point1 = new int[m]; int[] point2 = new int[m]; for (int i = 0; i < m; i++) { int x = scanner.nextInt(); int y = scanner.nextInt(); int length = scanner.nextInt(); edges[i] = new Edge(x - 1, y - 1, length); } Arrays.sort(edges); for (int i = 0; i < n; i++) { p[i] = i; } for (int i = 0; i < m; i++) { int x = find(p, edges[i].x); int y = find(p, edges[i].y); if (x == y) { continue; } else { p[x] = y; point1[sum] = edges[i].x + 1; point2[sum] = edges[i].y + 1; if (edges[i].length > totalLength) totalLength = edges[i].length; sum++; } } System.out.println(totalLength); System.out.println(sum); for (int i = 0; i < sum; i++) { System.out.println(point1[i] + " " + point2[i]); } } }用Java换一种方式实现

此代码是 Kruskal 算法的实现，它用于在无向图中寻找最小生成树。因此，我们可以用Prim算法来实现同样的功能。下面是使用Prim算法的Java代码实现：

import java.util.*;

public class lab1160 {
    static class Edge {
        int to, weight;

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

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        List<Edge>[] graph = new List[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 0; i < m; i++) {
            int x = scanner.nextInt() - 1;
            int y = scanner.nextInt() - 1;
            int length = scanner.nextInt();
            graph[x].add(new Edge(y, length));
            graph[y].add(new Edge(x, length));
        }

        PriorityQueue<Edge> pq = new PriorityQueue<>((a, b) -> a.weight - b.weight);
        boolean[] visited = new boolean[n];
        visited[0] = true;
        for (Edge e : graph[0]) {
            pq.offer(e);
        }
        int totalLength = 0;
        List<Integer> point1 = new ArrayList<>();
        List<Integer> point2 = new ArrayList<>();
        while (!pq.isEmpty()) {
            Edge e = pq.poll();
            if (visited[e.to]) {
                continue;
            }
            visited[e.to] = true;
            totalLength += e.weight;
            point1.add(Math.min(e.to + 1, e.weight + 1));
            point2.add(Math.max(e.to + 1, e.weight + 1));
            for (Edge next : graph[e.to]) {
                if (!visited[next.to]) {
                    pq.offer(next);
                }
            }
        }
        System.out.println(totalLength);
        System.out.println(point1.size());
        for (int i = 0; i < point1.size(); i++) {
            System.out.println(point1.get(i) + " " + point2.get(i));
        }
    }
}

这个实现中，我们使用了优先队列来维护当前未访问的边。我们从节点0开始，并将它标记为已访问。然后将所有与节点0相连的边加入队列中。每次从队列中取出权值最小的边，并将其目标节点标记为已访问。然后将所有与目标节点相连的未访问节点加入队列中。重复这个过程，直到所有节点都被访问。在这个过程中，我们记录了总权值和每个边的起点和终点，以便输出结果。