做了很多其他题，学习了一番，再回头看这道题，找出了很多可以优化的地方：
1. 对象Main d 可以去掉 pre[]和Find()可以用static静态调用，效果会更快。（快了5分）
2.可以新定义一个Edge类，使用结构化的方法来存储数据。List<Edge> list 来代替原来的ms数组，因为list中存储的是结构化的数据Edge的对象成员，调用起来会比原来二维数组ms要快。 （快了15分）
更新完是90分：代码如下：
import java.util.List; import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; class Edge implements Comparable<Edge>{ int s,e,length; Edge(int a,int b,int c){ s = a; e = b; length = c; } public int compareTo(Edge o) { return this.length - o.length; } } public class Main{ static List<Edge> list = new ArrayList<Edge>(); static int[] pre; public static int Find(int x){ int fx = x; while(pre[fx] != fx){ fx = pre[fx]; } int i = x,j; while(pre[i]!=fx){ j = pre[i]; pre[i] = fx; i = j; } return fx; } public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); // int[][] ms = new int[m][3]; int a,b,c; for (int i = 0; i < m; i++) { // for (int j = 0; j < 3; j++) { // ms[i][j] = sc.nextInt(); // // } a = sc.nextInt(); b = sc.nextInt(); c = sc.nextInt(); list.add(new Edge(a,b,c)); } // Main d = new Main(); pre = new int[n+1]; for (int i = 0; i <pre.length; i++) { pre[i] = i; } // Arrays.sort(ms, new Comparator<int[]>(){ // public int compare(int[] o1, int[] o2) { // return o1[2]-o2[2]; // } // } ); Collections.sort(list); int ans = 0; for (int i = 0; i < list.size(); i++) { // for (int i = 0; i < m; i++) { // int x = d.Find(ms[i][0]); // int y = d.Find(ms[i][1]); int x = Find(list.get(i).s); int y = Find(list.get(i).e); int length = list.get(i).length; if(x<y) pre[y]=x; else pre[x]=y; if(ans<length) ans = length; if(Find(n)==1) break; } System.out.println(ans); } }
以前的case如下：————————————————————————————————
代码：
import java.util.Comparator; import java.util.Arrays; import java.util.Collection; import java.util.Scanner; public class Main{ int[] pre; public int Find(int x){ int fx = x; while(pre[fx] != fx){ fx = pre[fx]; } int i = x,j; while(pre[i]!=fx){ j = pre[i]; pre[i] = fx; i = j; } return fx; } public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int[][] ms = new int[m][3]; for (int i = 0; i < m; i++) { for (int j = 0; j < 3; j++) { ms[i][j] = sc.nextInt(); } } Main d = new Main(); d.pre = new int[n+1]; for (int i = 0; i < d.pre.length; i++) { d.pre[i] = i; } Arrays.sort(ms, new Comparator<int[]>(){ public int compare(int[] o1, int[] o2) { return o1[2]-o2[2]; } } ); int ans = 0; for (int i = 0; i < ms.length; i++) { int x = d.Find(ms[i][0]); int y = d.Find(ms[i][1]); if(x<y) d.pre[y]=x; else d.pre[x]=y; if(ans<ms[i][2]) ans = ms[i][2]; if(d.Find(n)==1) break; } System.out.println(ans); } } 发现只能得到70分，超时严重？ ——然而用C++同样的方法不超时
想办法改进
不知道为什么 别人用对象跑出来的比我还要快点？
JAVA版：http://blog.csdn.net/YANG_Gang2017/article/details/71893237
而且当我把Main。d 改了 不用对象演算 结果还慢了？（被扣了5分）
同理的C++写出来的是可以跑满分的 很难：
C++版：http://blog.csdn.net/dream_never_giveup/article/details/67637488#comments
