poj1751 java

POJ 1751是一道经典的图论问题，题目描述如下：

给定一个无向图，图中有N个节点和M条边。每条边都有一个权值。现在需要在这个图中增加最少数量的边，使得图中的任意两个节点之间都有一条路径，并且增加边的总权值最小。

这是一个典型的最小生成树（Minimum Spanning Tree, MST）问题。解决这个问题的常用算法是Kruskal算法和Prim算法。这里我们使用Kruskal算法来解决问题。

Kruskal算法的基本步骤如下：
1. 将所有边按权值从小到大排序。
2. 初始化一个并查集（Union-Find Set），将每个节点作为一个独立的集合。
3. 依次选择权值最小的边，如果这条边连接的两个节点不在同一个集合中，则将这条边加入最小生成树，并将这两个节点所在的集合合并。
4. 重复步骤3，直到所有节点都在同一个集合中，或者已经选择了N-1条边（N是节点的数量）。

下面是一个Java实现的示例代码：

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int[] parent;

    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];
        parent = new int[N + 1];

        for (int i = 0; i < M; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            int cost = scanner.nextInt();
            edges[i] = new Edge(x, y, cost);
        }

        Arrays.sort(edges);

        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }

        int totalCost = 0;
        int edgeCount = 0;

        for (Edge edge : edges) {
            if (find(edge.x) != find(edge.y)) {
                union(edge.x, edge.y);
                totalCost += edge.cost;
                edgeCount++;
                if (edgeCount == N - 1) {
                    break;
                }
            }
        }

        System.out.println(totalCost);
        scanner.close();
    }

    static int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    static void union(int x, int y) {
        parent[find(x)] = find(y);
    }

    static class Edge implements Comparable<Edge> {
        int x, y, cost;

        Edge(int x, int y, int cost) {
            this.x = x;
            this.y = y;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge other) {
            return this.cost - other.cost;
        }
    }
}

这个代码首先读取节点和边的数量，然后读取每条边的信息并存储在Edge数组中。接着对边按权值进行排序，并初始化并查集。然后依次选择权值最小的边，如果这条边连接的两个节点不在同一个集合中，则将这条边加入最小生成树，并将这两个节点所在的集合合并。最终输出最小生成树的总权值。