import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main{
public static void main(String[] args)throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int n = pint(st.nextToken());
int m = pint(st.nextToken());
//간선 리스트..대신 크기가 주어지니 간선배열 사용
edge[] e = new edge[m];
for (int i = 0; i < m; i++) {
e[i]=new edge();
st = new StringTokenizer(br.readLine(), " ");
e[i].n1=pint(st.nextToken());
e[i].n2=pint(st.nextToken());
e[i].cost=pint(st.nextToken());
}
//정렬, 작은 간선부터 확인
Arrays.sort(e);
//분리집합 초기화
init(n);
int cnt=0, i=0;//현재 선택한 edge의 갯수, 현재 edge index
int totalCost=0;//전체cost
while(true) {
//union이 정상적으로 수행 됬다면 ( = cycle을 이루지 않는 간선이 tree에 포함되었다면)
if(union(e[i].n1, e[i].n2)) {
//cnt, cost 반영
cnt++;
totalCost+=e[i].cost;
}
if(cnt==n-1)break;//n-1개의 간선을 선택했다면 MST의 완성
i++;
}
//최소 cost의 2개의 마을로 분할하는 법 = MST에서 가장 cost가 큰 edge 하나 자르기
System.out.println(totalCost-e[i].cost);
}
//분리집합
static int[]parents;
static void init(int n) {
parents=new int[n+1];
for (int i = 0; i <= n; i++) {
parents[i]=i;
}
}
static int find(int n) {
if(parents[n]==n)return n;
return parents[n]=find(parents[n]);
}
static boolean union(int n1, int n2) {
int p1=find(n1);
int p2=find(n2);
if(p1==p2)return false;
parents[p1]=p2;
return true;
}
static int pint(String s) {
return Integer.parseInt(s);
}
//간선 객체
static class edge implements Comparable<edge>{
int n1;
int n2;
int cost;
@Override
public int compareTo(edge e) {
return this.cost-e.cost;
}
}
}
Prim 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main{
public static void main(String[] args)throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int n = pint(st.nextToken());
int m = pint(st.nextToken());
ArrayList<ArrayList<int[]>>graph = new ArrayList<>();
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<>());
}
//그래프 입력
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine(), " ");
int x = pint(st.nextToken());
int y = pint(st.nextToken());
int cost = pint(st.nextToken());
graph.get(x).add(new int[] {y,cost});
graph.get(y).add(new int[] {x,cost});
}
int totalCost=0, cnt=0, max=-1;
//전처리
boolean[] isV = new boolean[n+1];
PriorityQueue<int[]>pq = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
// TODO Auto-generated method stub
return o1[1]-o2[1];
}
});
for (int i = 1; i <= n; i++) {
pq.offer(new int[] {i,Integer.MAX_VALUE});
}
//임의의 시작 노드 설정
pq.offer(new int[] {1,0});
while(cnt!=n) {//n개의 정점을 선택하면 MST의 완성
int[] curNode = pq.poll();
if(isV[curNode[0]])continue;//이미 방문한 node면 무시한다
isV[curNode[0]]=true;
totalCost+=curNode[1];
if(max<curNode[1])max=curNode[1];//MST의 가장 큰 edge 저장
cnt++;
for (int i = 0; i < graph.get(curNode[0]).size(); i++) {
int[] next = graph.get(curNode[0]).get(i);
if(!isV[next[0]]) {
pq.offer(next);
}
}
}
System.out.println(totalCost-max);
}
static int pint(String s) {
return Integer.parseInt(s);
}
}
