CCF CSP认证 题解：201412-4 最优灌溉 Kruskal最小生成树+并查集（Java语言原创）

问题描述

　　雷雷承包了很多片麦田，为了灌溉这些麦田，雷雷在第一个麦田挖了一口很深的水井，所有的麦田都从这口井来引水灌溉。
　　为了灌溉，雷雷需要建立一些水渠，以连接水井和麦田，雷雷也可以利用部分麦田作为“中转站”，利用水渠连接不同的麦田，这样只要一片麦田能被灌溉，则与其连接的麦田也能被灌溉。
　　现在雷雷知道哪些麦田之间可以建设水渠和建设每个水渠所需要的费用（注意不是所有麦田之间都可以建立水渠）。请问灌溉所有麦田最少需要多少费用来修建水渠。

输入格式

　　输入的第一行包含两个正整数n, m，分别表示麦田的片数和雷雷可以建立的水渠的数量。麦田使用1, 2, 3, ……依次标号。
　　接下来m行，每行包含三个整数a _i, b _i, c _i，表示第a _i片麦田与第b _i片麦田之间可以建立一条水渠，所需要的费用为c _i。

输出格式

　　输出一行，包含一个整数，表示灌溉所有麦田所需要的最小费用。

样例输入

4 4
1 2 1
2 3 4
2 4 2
3 4 3

样例输出

6

样例说明

　　建立以下三条水渠：麦田1与麦田2、麦田2与麦田4、麦田4与麦田3。

import java.util.ArrayList;

import java.util.Collections;

import java.util.Scanner;

public class Main {

static int [] p;

public static void main(String[] args) {

Scanner in=new Scanner(System.in);

int n=in.nextInt();//n个点

int m=in.nextInt();//m条边

ArrayList<Edge>list=new ArrayList<Edge>();//记录无向边

for(int i=0;i<m;++i)

list.add(new Edge(in.nextInt(),in.nextInt(),in.nextInt()));

Collections.sort(list);//list内为Comparable接口对象 排序 

 

p=new int[n+1];//记录第i个点的父节点

for(int i=1;i<=n;i++)p[i]=i;//初始每个节点单独成树

int sum=0;

for(int i=0;i<list.size();++i){

int x=find(list.get(i).a);

int y=find(list.get(i).b);

if(x!=y){p[x]=y; 

sum+=list.get(i).day;

}

}

System.out.println(sum);

}

static public int find(int x){  //参照了刘汝佳《算法竞赛》一书写法

return  p[x]==x?x:(p[x]=find(p[x]));

}

}

class Edge implements Comparable<Edge>{

int a;

int b;

int day;

Edge(int a,int b,int day){

this.a=a;

this.b=b;

this.day=day;

}

public int compareTo(Edge e){//重写排序类比较方法

return(this.day-e.day);

}

}