[백준 6497] 전력난 - c++

문제링크: https://www.acmicpc.net/problem/6497

6497번: 전력난

---

문제 설명

성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들어가는데, 일부를 소등하여 그만큼의 돈을 절약할 수 있다.

그러나 만약 어떤 두 집을 왕래할 때, 불이 켜져 있지 않은 길을 반드시 지나야 한다면 위험하다. 그래서 도시에 있는 모든 두 집 쌍에 대해, 불이 켜진 길만으로 서로를 왕래할 수 있어야 한다.

위 조건을 지키면서 절약할 수 있는 최대 액수를 구하시오.

 

문제 조건

입력은 여러 개의 테스트 케이스로 구분되어 있다.

각 테스트 케이스의 첫째 줄에는 집의 수 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개 주어진다.

 

 

문제접근 - 최소비용신장트리

설치된 가로등의 비용이 최소화되게 하며 모든 집을 연결하면 된다.

최소비용신장트리를 사용하면 모든 집을 연결하면서 가로등의 비용을 최소화할 수 있다.

문제에서 절약할 수 있는 최대 액수를 구하라고 했으니,

가로등을 모두 켰을 때의 비용 - 최소화하여 킨 가로등의 비용을 구하면 된다. 

입력조건으로 간선의 갯수가 (노드의 갯수)^2 까지 주어지진 않으므로 크루스칼 알고리즘으로 구현하였다.

 

소스코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
 
// 간선 정보를 담을 배열 선언
typedef struct Edge{
    int u;
    int v;
    int w;
}edge;
 
// 입력간선을 받을 edge 배열 선언
vector<edge> edgeList;
 
// 연결된 노드의 집합을 표현할 배열 선언
int parent[200001];
 
// 집합 초기화 함수
void makeSet(int n){
    parent[n] = -1;
    return;
}
 
// 집합의 대표노드를 찾는 함수
int findSet(int n){
    if(parent[n] < 0)   return n;
    return parent[n] = findSet(parent[n]);
}
 
// 두 집합을 합치는 함수
int unionSet(int u, int v){
    int uSet = findSet(u);
    int vSet = findSet(v);
    if(uSet == vSet) return -1;
    
    parent[vSet] = uSet;
    return -parent[uSet];
}
 
// 최소비용을으로 마을을 연결하기 위한 크루스칼 알고리즘
long long kruskal(int m){
    int sz = int(edgeList.size());
    long long cost = 0; // 최소비용의 누적합
    int edgeCount = 0;
    
    for(int i=0; i<sz; i++){
        
        // u와 v가 연결되어 있지 않았으면 연결
        if(unionSet(edgeList[i].u, edgeList[i].v) > 0){
            cost += edgeList[i].w;      // 누적합에 현재 간선 가중치 더함
            if(++edgeCount == m-1)      // 연결간선이 노드 갯수-1 이면 연결간선의 누적합을 반환
                return cost;
        }
    }
    
    return 0;
}
 
 
bool cmp(const edge &a, const edge &b){
    return a.w < b.w ? true : false;
}
 
int main(){
    int n,m;
    // 전체 간선의 합을 구한다.
    int maxCount = 0;
    edge temp;
    
    while(cin >> m >> n){
        // 입력이 0 0 이면 종료
        if(m == 0 and n == 0)   break;
        edgeList.clear();
        maxCount = 0;
        
        for(int i=0; i<n; i++){
            cin >> temp.u >> temp.v >> temp.w;
            maxCount += temp.w;
            edgeList.push_back(temp);
            makeSet(i);
        }
        
        // 간선을 가중치를 기준으로 오름차순 정렬
        sort(edgeList.begin(), edgeList.end(),cmp);
        
        // 최대 절약비용 = 모든 간선의 합 - 최소비용 신장트리의 합
        cout << maxCount - kruskal(m) << endl;  // 결과 출력
    }
}