蓝桥杯历届试题-城市建设-最小生成树、并查集（Java代码）

解题思路:
将河道看成一个顶点
注意事项:
只要权值是负的 ，都要加入到最小生成树的边集中，生成数的边集数要加1；如果连接河道的边集只有一条边，那就把结果减去这条边的权值。
参考代码:

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

public class Main {
	static List<Edge> edgeList = new ArrayList<Edge>();
	static Set<Edge> T = new HashSet<>();
	static int n;
	static Map<Integer, UnionFind.UFNode> pntAndNode = new HashMap<Integer, UnionFind.UFNode>();
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		int m = sc.nextInt();
		while(m-- > 0 ){
			edgeList.add(new Edge(sc.nextInt(),sc.nextInt(),sc.nextInt()));
		}
		for(int i = 1; i <= n; i++){
			int dis = sc.nextInt();
			if(dis != -1){
				edgeList.add(new Edge(0,i,dis));
			}
		}
		buildMap();
		
		Set<Edge> t = getT();
		int res = 0;
		int count = 0;//记录河道的边数
		int cou = 0;//河道边的权值
		for (Edge edge : t) {
			if(edge.getEnd()==0){
				count++;
				cou = edge.getDistance();
			}
			if(edge.getStart() == 0){
				count++;
				cou = edge.getDistance();
			}
			res += edge.distance;
		}
		if(count == 1){//如果河道只有一条边
			res -= cou;//结果就减去这条边的权值
		}
		System.out.println(res);
	}
	private static Set<Edge> getT() {
		
		buildMis();
	
		return T;
	}
	private static void buildMis() {
		Collections.sort(edgeList);
		for (Edge e: edgeList) {
			if(!ok(e)){
				if(e.distance < 0){
					T.add(e);
					n +=1;
				}
				continue;
			}
			T.add(e);
			
			if(T.size() == n){
				return ;
			}
		}
	}
	private static boolean ok(Edge e) {
		UnionFind.UFNode x = pntAndNode.get(e.getStart());
		UnionFind.UFNode y = pntAndNode.get(e.getEnd());
		if(UnionFind.find(x) != UnionFind.find(y)){
			UnionFind.UnionNode(x, y);
			return true;
		}
		return false;
	}
	private static void buildMap() {
		for (Edge edge : edgeList) {
			pntAndNode.put(edge.start, new UnionFind.UFNode());
			pntAndNode.put(edge.end, new UnionFind.UFNode());
		}
	}

}
class UnionFind{ // 并查集
	public static UFNode find(UFNode x){
		UFNode p = x;
		Set<UFNode> n = new HashSet<>();
		while(p.parent != null){
			n.add(p);
			p = p.parent;
		}
		for (UFNode node : n) {
			node.parent = p;
		}
		return p;
	}
	public static void UnionNode(UFNode x,UFNode y){
		UnionFind.find(y).parent = UnionFind.find(x);
	}
	public static class UFNode{
		public UFNode parent;

		@Override
		public String toString() {
			return "UFNode [parent=" + parent + "]";
		}
		
	}
}
class Edge implements Comparable<Edge>{
	public Integer start;
	public Integer end;
	public Integer distance;
	
	public Edge(Integer start, Integer end, Integer distance) {
		super();
		this.start = start;
		this.end = end;
		this.distance = distance;
	}

	public Integer getStart() {
		return start;
	}

	public Integer getEnd() {
		return end;
	}

	public Integer getDistance() {
		return distance;
	}

	@Override
	public String toString() {
		return "Edge [start=" + start + ", end=" + end + ", distance=" + distance + "]";
	}

	@Override
	public int compareTo(Edge o) {
		// TODO Auto-generated method stub
		return this.distance - o.distance;
	}
	
}