CCF 201812-4 数据中心 Java

一、题目

问题描述

二、思路

待更新；并查集

三、代码

import java.util.*;
public class Main{
	static int[] parrent;
	static int max=0;
	static class edge implements Comparable<edge>{
		int p1,p2;
		int cost;
		edge(int p1,int p2,int cost){
			this.p1=p1;
			this.p2=p2;
			this.cost=cost;
		}
		public int compareTo(edge e){
			return this.cost-e.cost;
		}
	}
	static int find(int x){
		while(x!=parrent[x]){
			parrent[x]=parrent[parrent[x]];
			x=parrent[x];
		}
		return x;
	}
	static boolean unite(int x,int y){
		x=find(x);
		y=find(y);
		if(x!=y) {
			parrent[x]=y;
			return true;
		}
		return false;
	}
	public static void main(String[] args){
		Scanner in=new Scanner(System.in);
		int node=in.nextInt();
		int num=in.nextInt();
		int root=in.nextInt();
		edge[] arr=new edge[num];
		parrent=new int[num];
		for(int i=0;i<num;i++)
			parrent[i]=i;
		for(int i=0;i<num;i++){
			int e1=in.nextInt();
			int e2=in.nextInt();
			int c=in.nextInt();
			arr[i]=new edge(e1,e2,c);
		}
		Arrays.sort(arr);
		for(int i=0;i<num;i++){
			edge e=arr[i];
			if(unite(e.p1,e.p2)){
				max=e.cost;
				node--;
			}
			if(node==1) break;
			
		}
		System.out.println(max);
	}
}