Java求助!关于算法的输入问题
  • 板块学术版
  • 楼主doubleble
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/11/12 15:28
  • 上次更新2024/11/12 19:09:23
查看原帖
Java求助!关于算法的输入问题
507444
doubleble楼主2024/11/12 15:28

不知道大家有没有遇到就是java程序一次性输入太多,读取数据异常的问题。例如P1525 [NOIP2010 提高组] 关押罪犯 。大家只需要看一下输入代码,我下载了一个re的数据,其中输入有10w条数据,然后我去本地执行,我发现n的数据就有问题,应该就是一次性输入太多数据了。按理来说n应该是10000,m是100000,但是输出n和m的值是对不上的。这个该怎么解决,而且网站里面这种大量输入的还挺多的。

    static int[] arr;
    public static int find(int i){
        return i == arr[i] ? i : (arr[i] = find(arr[i]));
    }
    public static void union(int i , int j){
        int fx = arr[i];
        int fy = arr[j];
        if(fx != fy)
            arr[fx] = fy;
    }
    static class fight implements Comparable<fight>{
        int zuo;
        int you;
        int fight;
        public fight(int zuo , int you , int fight){
            this.zuo = Math.min(zuo , you);
            this.you = Math.max(zuo , you);
            this.fight = fight;
        }

        @Override
        public int compareTo(fight o) {
            return Integer.compare(o.fight , this.fight);
        }
    }
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();//输入n和m
        int m = sc.nextInt();
        System.out.println(n);//打印
        System.out.println(m);
        List<fight> lists = new LinkedList<>();
        arr = new int[n + 1];
        int[] brr = new int[n + 1];
        for(int i = 1 ; i <= n ; i++){//初始化并查集
            arr[i] = i;
            brr[i] = i;
        }
        for(int i = 1 ; i <= m ; i++) lists.add(new fight(sc.nextInt() , sc.nextInt() , sc.nextInt()));

        Collections.sort(lists);//排序
        for(int i = 0 ; i < lists.size() ; i++){
            fight fight = lists.get(i);
            int zuo = fight.zuo;
            int you = fight.you;
            int fi = fight.fight;
            if(find(zuo) == find(you)){//同监狱直接输出
                System.out.println(fi);
                return;
            }else {
                if(brr[zuo] == zuo) brr[zuo] = you;
                else union(you , brr[zuo]);
                if(brr[you] == you) brr[you] = zuo;
                else union(zuo , brr[you]);
            }
        }
        System.out.println(0);
    }
2024/11/12 15:28
加载中...