[백준/C++] 6497번. 전력난
1. 문제
성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들어가는데, 일부를 소등하여 그만큼의 돈을 절약할 수 있다.
그러나 만약 어떤 두 집을 왕래할 때, 불이 켜져 있지 않은 길을 반드시 지나야 한다면 위험하다. 그래서 도시에 있는 모든 두 집 쌍에 대해, 불이 켜진 길만으로 서로를 왕래할 수 있어야 한다.
위 조건을 지키면서 절약할 수 있는 최대 액수를 구하시오.
2. 입력
입력은 여러 개의 테스트 케이스로 구분되어 있다.
각 테스트 케이스의 첫째 줄에는 집의 수 m과 길의 수 n이 주어진다. (1 ≤ m ≤ 200000, m-1 ≤ n ≤ 200000)
이어서 n개의 줄에 각 길에 대한 정보 x, y, z가 주어지는데, 이는 x번 집과 y번 집 사이에 양방향 도로가 있으며 그 거리가 z미터라는 뜻이다. (0 ≤ x, y < m, x ≠ y)
도시는 항상 연결 그래프의 형태이고(즉, 어떤 두 집을 골라도 서로 왕래할 수 있는 경로가 있다), 도시상의 모든 길의 거리 합은 231미터보다 작다.
입력의 끝에서는 첫 줄에 0이 2개 주어진다.
3. 출력
각 테스트 케이스마다 한 줄에 걸쳐 절약할 수 있는 최대 비용을 출력한다.
4. 풀이
- 최소 신장 트리 문제
m,n을 입력받는while-loop를 만들고m과n이 모두 0일 때까지 반복한다.parernt배열을 자기 자신으로 초기화 해준다.m개의 도로 정보를 받아 온다.
도로 정보를 받아오면서 비용의 총합을 미리 구해둔다- 도로 정보를 비용 오름차순으로 정렬한다.
비용이 적은 도로를 우선 건설하기 위함 - 도로 정보를 하나씩 가져 오면서 사이클이 생기지 않는
(=부모가 같지 않은)도로를 건설한다.
건설한 도로 비용을 더해서 구한다. - 도로를 건설했다면 두 마을을 합집합한다.
- 모든 도로를 건설하는데 드는 비용에서 새로 건설한 도로의 비용을
빼면 절약한 비용이 나온다.
5. 처음 코드와 달라진 점
parent배열을 초기화 해주지 않아서 수정했다.
6. 코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int parent[200000];
int findParent(int x) {
if (x == parent[x]) return x;
else return parent[x] = findParent(parent[x]);
}
void unionParent(int a, int b) {
a = findParent(a);
b = findParent(b);
if (a < b) parent[b] = a;
else parent[a] = b;
}
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
while (true) {
vector<pair<int, pair<int, int> > > v;
int m, n;
cin >> m >> n;
if (m == 0 && n == 0) break;
for (int i = 0; i < n; i++) {
parent[i] = i;
}
int totalCost = 0;
for (int i = 0; i < n; i++) {
int a, b, cost;
cin >> a >> b >> cost;
totalCost += cost;
v.push_back(make_pair(cost, make_pair(a, b)));
}
sort(v.begin(), v.end());
int newCost = 0;
for (int i = 0; i < v.size(); i++) {
int a = v[i].second.first;
int b = v[i].second.second;
int cost = v[i].first;
if (findParent(a) != findParent(b)) {
newCost += cost;
unionParent(a, b);
}
}
cout << totalCost - newCost<<endl;
}
}