白駿1647都市分割計画
19714 ワード
[白駿1647都市分割計画(https://www.acmicpc.net/problem/1647)
白駿1647都市分割計画
実施前の考え方
クルーズアルゴリズムを用いて重みが最も低い経路を見つけ,重みが最も大きい経路の行く手を切断して2つの村を形成した.
残念な点
最後に重み付けを減算する->最後の前に探索する方法よりも,コードをより簡便に記述できる.
それからクルーズのアルゴリズムをよく知っています.
コード#コード#
package backjoon_4월;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
import javax.swing.InputMap;
public class 백준_1647_도시분할계획 {
static int N, M;
static ArrayList<ArrayList<Edge>> list=new ArrayList<>();
static Edge[] edgeList;
static int parents[];
static class Edge implements Comparable<Edge>{
int weight,from,to;
public Edge( int from, int to,int weight) {
this.weight = weight;
this.from = from;
this.to = to;
}
@Override
public int compareTo(Edge o) {
return Integer.compare(this.weight, o.weight);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
parents = new int[N+1];
edgeList = new Edge[M];
for (int i = 0; i < M; i++) {
st =new StringTokenizer(br.readLine()," ");
int from =Integer.parseInt(st.nextToken());
int to =Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
edgeList[i] =new Edge (from , to , weight);
}
Arrays.sort(edgeList);
make();
int result = 0;
int count = 0;
int max =-1;
for(Edge edge : edgeList) {
if(union(edge.from, edge.to)) { //사이클 발생 x
result += edge.weight;
count++;
}
if (count == N-2) {
break;
}
}
System.out.println(result);
//System.out.println(result-max);
}
static int findSet(int a) {
//들오온 a가 대표자라면
if(parents[a]==a) return a;
// return findSet(parents[a]); //path compression 전
return parents[a] = findSet(parents[a]); //path compression 후
}
public static void make() {
for (int i = 0; i <= N; i++) {
parents[i]=i;
}
}
public static boolean union(int a , int b) {
int aRoot = findSet(a);
int bRoot = findSet(b);
if(aRoot==bRoot) return false;
parents[bRoot] = aRoot;
return true;
}
}
Reference
この問題について(白駿1647都市分割計画), 我々は、より多くの情報をここで見つけました https://velog.io/@jeus95/백준-1647-도시분할계획テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol