質問する

動物園から逃げ出したばかりのサルが世界を一周している.それから平和な村に行って、そこで未知のことが起こりました.
村はN軒の家とそれらの家を結ぶM本の道で構成されている.道はどんな方向にも通行できる歩道です.そしてどの道にも維持費があります.
村の里長は村を二つの別々の村に分割する計画だ.村が大きすぎて、一人では管理できません.村を分割するときは、別々の村の家屋を互いにつながっている部分に分割します.これは、分離された村ごとに任意の2つの家の間に必ず道があることを意味します.村には1軒以上の家が必要だ.
こうして、村の里長は計画を立てているうちに、村の道が多すぎると思った.いったん離れた2つの村の間の道は必要なく、取り除くことができます.そして、それぞれの離れた村には、任意の2つの家の間の経路が常に存在し、道路をさらに解消することができる.村の里長は上記の条件を満たすために、すべての道を除いて、残りの道の維持費の和を最小限に抑えたいと思っています.これを求めるプログラムを書いてください.

入力

1行目は家の個数N,道の個数Mを与える.Nは2以上100000以下の整数、Mは1以上100000以下の整数である.次の行から、M行では、道の情報にABCの3つの整数が与えられ、A号家とB号家を結ぶ道の維持費がC(1≦C≦1000)であることを示す.

しゅつりょく

1行目を外し、残りの道路料金プロトコルの最高値を出力します.

I/O例

に答える

Union Findを使用したKruskalアルゴリズムの実装
村を分離するために、グラフにマージする前に、マージのコストが増加しました.

コード#コード#

import java.io.*;
import java.util.*;

public class Main {
	static int[]p;
	static class Edge implements Comparable<Edge>{
		public int start,end,weight;

		public Edge(int start, int end, int weight) {
			this.start = start;
			this.end = end;
			this.weight = weight;
		}
		@Override
		public int compareTo(Edge o) {
			return this.weight-o.weight;
		}
	}
	static int find(int x) {
		if(x==p[x])return x;
		return p[x]=find(p[x]);
	}
	static boolean union(int x,int y) {
		int a=find(x);
		int b=find(y);
		
		if(a==b)return false;
		p[b]=a;
		return true;
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n=Integer.parseInt(st.nextToken());
		int m=Integer.parseInt(st.nextToken());
		p=new int[n+1];
		for(int i=1;i<=n;i++) {
			p[i]=i;
		}
		Edge[]edgeList = new Edge[m];
		int x,y,w;
		while(m-->0) {
			st=new StringTokenizer(br.readLine());
			x=Integer.parseInt(st.nextToken());
			y=Integer.parseInt(st.nextToken());
			w=Integer.parseInt(st.nextToken());
			edgeList[m]=new Edge(x,y,w);
		}
		Arrays.sort(edgeList);
		int result=0,cnt=0;
		for(Edge edge:edgeList) {
			if(union(edge.start, edge.end)) {
				result+=edge.weight;
				if(++cnt==n-2)break;
			}
		}
		System.out.println(result);
	}
}