这就是一个最短路 ，排一下序然后并查集start和end就行了，要是用c++做估计我10分钟就能做完，但是这个学期学java，那就用java吧，感觉好难啊 -- ， 静态 动态这一块，上下文这一块。。。。。
import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; public class Main{ static class node{ //每一条路径 int start,end; int cost; node(int x,int y){ this.start = x; this.end = y; } node(int x,int y,int z){ this.start = x; this.end = y; this.cost = z; } } static node f[] = new node[3010]; static int n,m,cost; static int[] mark = new int[3010]; private static void init(){ for(int i=0;i<=n;i++){ mark[i]=i; } } private static int getf(int x){ if(mark[x]==x) return x; else{ mark[x]=getf(mark[x]); return mark[x]; } } private static int merge(int u,int v){ int t1=getf(u); int t2=getf(v); if(t1==t2) return 0; else{ mark[t1]=t2; return 1; } } public static void main(String[] args){ Scanner in =new Scanner(System.in); n = in.nextInt(); m = in.nextInt(); init(); for(int i=1;i<=m;i++){ int a=in.nextInt(); int b=in.nextInt(); int c=in.nextInt(); f[i] =new node(a,b,c); } Arrays.sort(f,1,m+1,new Comparator<node>() { @Override public int compare(node a,node b){ if(a.cost<b.cost) return -1; else if(a.cost==b.cost) return 0; else return 1; } }); //for(int i=1;i<=m;i++){ // System.out.println(f[i].cost); //} int sum=0,cnt=n; for(int i=1;i<=m && cnt>1;i++){ if(merge(f[i].start, f[i].end)==1){ sum+=f[i].cost; cnt--; //System.out.println(cnt); } } //for(int i=1;i<=n;i++){ // System.out.println(getf(mark[i])); //} if(cnt==1) System.out.println(sum); else System.out.println(-1); in.close(); } }
