ylsn123456 @ 2022-08-28 20:33:05
这对Java也太不友好了,和C/C++一样的空间,时间限制。。。。。8,9,10卡在了内存边界上(MLE)
稍微改了一下,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不友好很正常