这对Java也太不友好了(MLE)

P3366 【模板】最小生成树

ylsn123456 @ 2022-08-28 20:33:05

  1. 这对Java也太不友好了,和C/C++一样的空间,时间限制。。。。。8,9,10卡在了内存边界上(MLE)

  2. 稍微改了一下,9,10能过了,但是8还是不行,都在内存边界边缘

import java.util.*;

public class P3366最小生成树 {
    //根据边来做
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] s = sc.nextLine().split(" ");
        int N = Integer.parseInt(s[0]);
        int M = Integer.parseInt(s[1]);
        Solution ss = new Solution(N);
        long ans = ss.jisuan(M, sc);
        if(ss.size==1){
            System.out.println(ans);
        }else{
            System.out.println("orz");
        }

    }
}
class Edge{
    int a,b,d;
    public Edge(int a1,int b1,int d1){
        a = a1;
        b = b1;
        d = d1;
    }
}
class Solution{
    int size;
    int n;
    PriorityQueue<Edge> pq = new PriorityQueue<>(new Comparator<Edge>() {
        @Override
        public int compare(Edge o1, Edge o2) {
            return o1.d-o2.d;
        }
    });

    long jisuan(int M,Scanner sc){
        for (int i = 0; i < M; i++) {
            String[] s1 = sc.nextLine().split(" ");
            int x = Integer.parseInt(s1[0])-1;
            int y = Integer.parseInt(s1[1])-1;
            int d = Integer.parseInt(s1[2]);
            pq.add(new Edge(x,y,d));
        }

        long ans = 0;
        while(!pq.isEmpty()){
            Edge cur = pq.poll();
            if(collect(cur.a,cur.b)) continue;
            ans+=cur.d;
            union(cur.a,cur.b);
        }
        return ans;
    }

    public Solution(int n){
        this.n = n;
        size = n;
        p = new int[n];
        for(int i=0;i<n;i++){
            p[i] = i;
        }
    }

    boolean collect(int a,int b){
        int r1 = find(a);
        int r2 = find(b);
        return r1==r2;
    }

    void union(int a,int b){
        int r1 = find(a);
        int r2 = find(b);
        if(r1==r2) return;
        p[r2] = r1;
        size--;
    }

    int[] p;
    int find(int i){
        if(p[i]!=i){
            p[i] = find(p[i]);
        }
        return p[i];
    }
}

by sunrise1024 @ 2022-08-28 20:45:59

@ylsn123456 因为说西西弗的比赛都不让用Java,而洛谷又是个OI网站,对Java不友好很正常


|