백준 14950번: 정복자 (C++)

https://www.acmicpc.net/problem/14950

14950번: 정복자

---

Solved By: Kruskal Algorithm

 

정복할 때마다 도로 비용을 t만큼 올린다 한들 모든 도로가 t만큼 올라가는 것이기 때문에 우선 어떤 노드에서 다른 모든 노드를 갈 수 있으며 가중치가 최소인 합을 구해야 합니다.

>> 즉, MST를 구해야 합니다. Kruskal Algorithm 사용

 

최소합을 구한 상태에서 t값을 신경 써줘야 하는데

MST의 edge의 개수는 n - 1개입니다.

첫 도로는 t값의 영향을 받지 않기에 2번째 도로부터 t값이 올라갑니다.

>> 2번 도로 = t, 3번 도로 = 2 * t, n - 1번 도로 = (n - 2) * t입니다.

 

등차수열의 합으로 항은 (n - 2)개이며, 첫째항은 t, 공차가 t인 등차수열의 합을 구해주면 됩니다.

그리고, 이 합을 결과값에 더해주면 답이 됩니다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#define pii pair<int, int>
#define MAX 10001
using namespace std;

vector<pair<pii, int>> edges;
int parent[MAX];
int n, m, t;

bool cmp(pair<pii, int> a, pair<pii, int> b){
    return a.second < b.second;
}

int getRoot(int node){
    if(node == parent[node]) return node;
    return parent[node] = getRoot(parent[node]);
}

bool find(int a, int b){
    int ga = getRoot(a);
    int gb = getRoot(b);
    
    if(ga != gb) return true;
    else return false;
}

void unionNodes(int a, int b){
    int ga = getRoot(a);
    int gb = getRoot(b);
    
    if(ga < gb) parent[gb] = ga;
    else parent[ga] = gb;
}

int main(){
    cin >> n >> m >> t;
    for(int i = 0; i < m; i++){
        int a, b, w; cin >> a >> b >> w;
        edges.push_back({{a, b}, w});
    }
    
    sort(edges.begin(), edges.end(), cmp);
    
    for(int i = 1; i <= n; i++) parent[i] = i;
    
    int result = 0;
    
    for(int i = 0; i < edges.size(); i++){
        if(find(edges[i].first.first, edges[i].first.second)){
            unionNodes(edges[i].first.first, edges[i].first.second);
            result += edges[i].second;
        }
    }
    
    // 등차수열의 합
    result += (n - 2) * (2 * t + (n - 3) * t) / 2;
    cout << result;
    return 0;
}