克鲁斯卡尔解决-道路建设(MST)

Java克鲁斯卡尔解决-道路建设(MST)

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

public class Main {
    static class Edge {
        int a, b, c;

        public Edge(int a, int b, int c) {
            super();
            this.a = a;
            this.b = b;
            this.c = c;
        }

    }

    static int[] f = new int[105];
    static int m;// 城市数目

    // 并查集初始化
    public static void init() {
        for (int i = 1; i <= m; i++) {
            f[i] = i;
        }
    }

    public static int find(int x) {
        if (f[x] == x)
            return x;
        return f[x] = find(f[x]);// 路径压缩
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int c = sc.nextInt();
            int n = sc.nextInt();
            m = sc.nextInt();
            init();// 并查集初始化
            Edge[] edges = new Edge[n];
            for (int i = 0; i < edges.length; i++) {
                edges[i] = new Edge(sc.nextInt(), sc.nextInt(), sc.nextInt());
            }
            // 按照边长从小到大排序
            Arrays.sort(edges, new Comparator<Edge>() {
                @Override
                public int compare(Edge a, Edge b) {
                    return a.c - b.c;
                }
            });
            int cnt = 0;// 统计总共取了几条边
            int sum = 0;
            // 枚举每一条边
            for (int i = 0; i < edges.length; i++) {
                int fa = find(edges[i].a);
                int fb = find(edges[i].b);
                // 如果这条边的两个端点没有连通，取这条边，让这两个点连通
                if (fa != fb) {
                    f[fa] = fb;
                    cnt++;
                    sum += edges[i].c;
                }
                if (cnt == m - 1)
                    break;
            }
            if (sum > c)
                System.out.println("No");
            else
                System.out.println("Yes");
        }
    }
}