本文主要是介绍CCF CSP认证 题解：201412-4 最优灌溉 Kruskal最小生成树+并查集（Java语言原创），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
为了灌溉，雷雷需要建立一些水渠，以连接水井和麦田，雷雷也可以利用部分麦田作为“中转站”，利用水渠连接不同的麦田，这样只要一片麦田能被灌溉，则与其连接的麦田也能被灌溉。
现在雷雷知道哪些麦田之间可以建设水渠和建设每个水渠所需要的费用（注意不是所有麦田之间都可以建立水渠）。请问灌溉所有麦田最少需要多少费用来修建水渠。
接下来m行，每行包含三个整数a i, b i, c i，表示第a i片麦田与第b i片麦田之间可以建立一条水渠，所需要的费用为c i。
1 2 1
2 3 4
2 4 2
3 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);
}
}
这篇关于CCF CSP认证 题解：201412-4 最优灌溉 Kruskal最小生成树+并查集（Java语言原创）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
