[백준] 6497 전력난

6497번: 전력난

 

boj.kr

풀이

MST로 풀 수 있는 문제이다. 문제는 도시에서 절약할 수 있는 최대 액수를 구하는 것이고 이는 최소 액수로 가로등을 키는 문제라고 생각할 수 있다. 따라서 kruskal 알고리즘을 통해 가로등을 키는데 필요한 비용을 계산하고, 전체 비용에서 빼주면 된다.

코드

C++

	#include <iostream>
	#include <vector>
	#include <algorithm>
	using namespace std;
	int m, n;
	vector<pair<int, pair<int, int>>> edges;
	int parent[200001];
	int find(int x) {
	if (x == parent[x]) return x;
	return parent[x] = find(parent[x]);
	}
	void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a < b) parent[b] = a;
	else parent[a] = b;
	}
	int kruskal() {
	sort(edges.begin(), edges.end());
	int sum = 0;
	for (int i = 0; i < n; i++) {
	int x = edges[i].second.first;
	int y = edges[i].second.second;
	int dist = edges[i].first;
	if (find(x) == find(y)) continue;
	merge(x, y);
	sum += dist;
	}
	return sum;
	}
	int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	while (true) {
	cin >> m >> n;
	if (m == 0 && n == 0) break;
	edges.clear();
	for (int i = 1; i <= m; i++) parent[i] = i;
	int total_dist = 0;
	for (int i = 0; i < n; i++) {
	int x, y, z;
	cin >> x >> y >> z;
	edges.push_back({ z, {x, y} });
	total_dist += z;
	}
	cout << total_dist - kruskal() << '\n';
	}
	return 0;
	}

view raw 6497.cpp hosted with ❤ by GitHub

Python3

	import sys
	input = sys.stdin
	def find(x):
	if x != parent[x]:
	parent[x] = find(parent[x])
	return parent[x]
	def union(a, b):
	a = find(a)
	b = find(b)
	if a < b:
	parent[b] = a
	else:
	parent[a] = b
	def kruskal():
	edges.sort()
	sum = 0
	for i in edges:
	x = i[1][0]
	y = i[1][1]
	dist = i[0]
	if find(x) == find(y):
	continue
	sum += dist
	union(x, y)
	return sum
	while True:
	m, n = map(int, input.readline().rstrip().split())
	if m == 0 and n == 0:
	break
	parent = [0] * (m + 1)
	edges = []
	for i in range(1, m + 1):
	parent[i] = i
	total_dist = 0
	for _ in range(n):
	x, y, z = map(int, input.readline().rstrip().split())
	edges.append((z, (x, y)))
	total_dist += z
	print(total_dist - kruskal())

view raw 6497.py hosted with ❤ by GitHub