https://www.acmicpc.net/problem/14950
14950번: 정복자
서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재한다. 각각 도시는 1번부터 N번까지 번호가 붙여져 있다. 그 중에서 1번 도시의 군주 박건은 모든 도시를 정복하고 싶어한다. 처음 점거하고 있는 도시는 1번 도시 뿐이다. 만약 특정 도시 B를 정복하고 싶다면, B와 도로로 연결된 도시들 중에서 적어도 하나를 정복하고
www.acmicpc.net
단순 MST 인줄 알았는데..
예외 변수가 하나 있음.
도로 건설시 추가 비용 t가 발생하는데.
조건을 따져 보면. (1~n-1 까지의 합) x t가 증가하는 비용으로 고정됨.
(N-1)! * t = 고정비용 임
(1~n-1 합은) = ((n-2)*(n-1)/2) * t
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class BOJ14950 {
static int N, M, T;
static Edge[] edges;
static DJS djs;
static class Edge implements Comparable<Edge> {
int s, e, v;
Edge(int s, int e, int v){
this.s=s;
this.e=e;
this.v=v;
}
@Override
public int compareTo(Edge o) {
return this.v-o.v;
}
}
static class DJS{
int[] mom;
DJS(int n) {
mom = new int[n+1];
for (int i = 1; i < n+1 ; i++) mom[i] = i;
}
int find(int n) {
if(n==mom[n]) return n;
return mom[n] = find(mom[n]);
}
boolean union(int a, int b){
a = find(a);
b = find(b);
if(a==b) return false;
mom[b] = a;
return true;
}
}
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("res/input_boj14950.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
T = Integer.parseInt(st.nextToken());
djs = new DJS(N);
edges = new Edge[M];
int a, b, c;
for (int i = 0; i < M ; i++) {
st = new StringTokenizer(br.readLine().trim(), " ");
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
edges[i] = new Edge(a, b, c);
}
Arrays.sort(edges);
long result = 0;
int cnt = 0;
for (Edge ed:edges) {
if(djs.union(ed.s,ed.e)){
result+=ed.v;
cnt++;
}
if(cnt== N-1) break;
}
result+= (((N-2)*(N-1)/2) * T);
System.out.println(result);
}
}