MLE什么鬼?
查看原帖
MLE什么鬼?
527347
jasper2021楼主2021/9/10 17:13

什么鬼?

哪位大神能指点一下,还要怎么优化?

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

public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt(), m = cin.nextInt();
        int[][] xyt = new int[m][3];
        for (int[] z : xyt) {
            z[0] = cin.nextInt();
            z[1] = cin.nextInt();
            z[2] = cin.nextInt();
        }
        cin.close();
        
        Arrays.sort(xyt, (a,b)->a[2]-b[2]);
        
        int ans = 0;
        UF uf = new UF(n);
        if (uf.count > 1) {
            ans = -1;
            for (int[] z : xyt) {
                uf.union(z[0]-1, z[1]-1);
                if (uf.count==1) {
                    ans = z[2];
                    break;
                }
            }
        }
        
        System.out.println(ans);
    }
}

class UF {
    int[] parent;
    int count;
    
    UF(int n) {
        count = n;
        parent = new int[n];
        for (int i=0; i<n; i++)
            parent[i] = i;
    }
    
    int find(int p) {
        while (p != parent[p]) {
            p = parent[p] = parent[parent[p]];
        }
        return p;
    }
    
    void union(int p, int q) {
        int rootP = find(p), rootQ = find(q);
        if (rootP==rootQ) return ;
        count--;
        parent[rootP] = rootQ;
    }
}
2021/9/10 17:13
加载中...