蓝桥杯历届试题-国王的烦恼 （Java代码）

解题思路:

哪里有问题呀！只能过55%

注意事项:

参考代码:

import java.util.Arrays;

import java.util.Comparator;

import java.util.Scanner;

public class Main {

    private static int N;

    static int a[]=new int[11002];

    private static int count=0;

    private static Integer[][] b;

    private static Integer pre=-1;

public static void main(String[] args) {

    Scanner input=new Scanner(System.in);

    N=input.nextInt();

    int M=input.nextInt();

   b=new Integer[100002][3];

   for (int i = 1; i <=N; i++) {

    a[i]=i;

}

   for (int i = 1; i <=M; i++) {

    b[i][0]=input.nextInt();

    b[i][1]=input.nextInt();

    b[i][2]=input.nextInt();

}

   Arrays.sort(b,1,M+1,new Comparator<Integer[]>(){//从大到小排序

    @Override

    public int compare(Integer[] o1, Integer[] o2) {

    if(o1[2]>o2[2])

    return -1;

    else if(o1[2]<o2[2]){

    return 1;

    }

    else

    return 0;

    }

   });

    for (int i = 1; i <M+1; i++) {

    int way=unit(b[i][0],b[i][1]);

    if(pre!=b[i][2]&&way==1){

    count++;//记录次数

    pre=b[i][2];//改变天数

    }

}

  System.out.println(count);

}

private static int unit(Integer a1, Integer b1) {

    a1=find(a1);

    b1=find(b1);

    if(a1!=b1){

    a[b1]=a1;

    return 1;

    }

return 0;

}

private static Integer find(Integer a2) {

    if(a2==a[a2])return a2;

    else

    return  a[a2]=find(a[a2]);

}

}