小美的修路
https://ac.nowcoder.com/acm/problem/261579
有没有大佬帮忙看看,为什么这个的通过率只有10% 找不出逻辑错误了
import java.util.Scanner; import java.util.Arrays; import java.util.HashSet; import java.util.LinkedList; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { private static int[] father; static final int N = (int)1e5 + 10; public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 int n = in.nextInt(); // 城市数量 int m = in.nextInt(); // 可选择的计划的数量 int[][] roads = new int[m][5]; for (int i = 0; i < m; i++) { roads[i][0] = i + 1; roads[i][1] = in.nextInt(); roads[i][2] = in.nextInt(); roads[i][3] = in.nextInt(); roads[i][4] = in.nextInt(); } Arrays.sort(roads, (int[] a, int[] b) -> { if (a[4] != b[4]) { return Integer.compare(b[4], a[4]); // 最后一列为1的排在前面 } else { return Integer.compare(a[3], b[3]); // 最后一列相同时按第三列排序 } }); int sum = 0; father = new int[N]; init(); HashSet<Integer> set = new HashSet<>(); LinkedList<Integer> list = new LinkedList<>(); for (int i = 0; i < m; i++) { if (roads[i][4] == 1) { join(roads[i][1], roads[i][2]); set.add(roads[i][1]); set.add(roads[i][2]); sum++; list.add(roads[i][0]); } else { if (isSame(roads[i][1], roads[i][2])) { continue; } else { join(roads[i][1], roads[i][2]); sum++; set.add(roads[i][1]); set.add(roads[i][2]); list.add(roads[i][0]); } } if (set.size() == n) { break; } } if (set.size() < n) { System.out.println(-1); } else { System.out.println(sum); for (int j = 0; j < list.size(); j++) { System.out.print(list.get(j)); System.out.print(" "); } } } public static void init() { for (int i = 0; i < father.length; i++) { father[i] = i; } } public static int find(int u) { if (u == father[u]) { return u; } else { father[u] = find(father[u]); return father[u]; } } public static boolean isSame(int u, int v) { return find(u) == find(v); } public static void join(int u, int v) { u = find(u); v = find(v); if (u == v) { return; } else { father[v] = u; } } }#刷题找工作啊##刷题日记#