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 BOJ6497 {
static int N, M;
static DJS djs;
static Edge[] edges;
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 ; i++) mom[i] = i;
}
public int find(int n) {
if(n==mom[n]) return n;
return mom[n] = find(mom[n]);
}
public 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_boj6497.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
while (true) {
st = new StringTokenizer(br.readLine().trim(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
if(N+M == 0) break;
djs = new DJS(N);
edges = new Edge[M];
int a, b, c;
long total = 0;
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);
total += c;
}
Arrays.sort(edges);
long result = 0;
for (Edge ed: edges) {
if(djs.union(ed.s, ed.e)) result += ed.v;
}
System.out.println(total-result);
}
}
}
https://www.acmicpc.net/problem/6497
6497번: 전력난
문제 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 원래 모든 길마다 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들어가는데, 일부를 소등하여 그만큼의 돈을 절약할 수 있다. 그러나 만약 어떤 두 집을 왕래할 때, 불이 켜져 있지 않은 길을 반드시 지나야 한다면 위험하다. 그래서 도시에 있는 모든 두 집 쌍에 대해, 불이 켜진 길만으로 서로를 왕래할 수 있어야 한다. 위 조건을 지
www.acmicpc.net
총 거리에서 MST를 빼면, 그값이 절약하는 최대 값이 됨.