[14950번] 정복자

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 최소 스패닝 트리

이 문제는 1번 정점부터 시작이라 했으니 프림 알고리즘으로 다가가도 되지만

결국 최소 스패닝 트리를 이룰 때 1번정점과 다른 정점의 최소 간선을 이어주기에 크루스칼을 이용해도 무방하다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
 
using namespace std;
 
typedef struct _KS_ {
    int from;
    int to;
    int val;
}KS;
 
vector<KS> edge;
 
int chk[10002];
int ret;
 
bool comp(KS a, KS b)
{
    return a.val < b.val;
}
 
int find(int num)
{
    if (num == chk[num])
        return num;
 
    return chk[num] = find(chk[num]);
}
 
int main()
{
    int n, m, t;
    scanf("%d %d %d", &n, &m, &t);
 
    for (int i = 1; i <= n; i++)
        chk[i] = i;
 
    for (int i = 0; i < m; i++)
    {
        KS ks;
        scanf("%d %d %d", &ks.from, &ks.to, &ks.val);
 
        edge.push_back(ks);
    }
 
    sort(edge.begin(), edge.end(), comp);
 
    int cnt = 0;
    for (int i = 0; i < m; i++)
    {
        int nv = find(edge[i].from);
        int nw = find(edge[i].to);
 
        if (nv == nw)
            continue;
 
        chk[nv] = nw;
 
        ret += edge[i].val + t * (cnt++);
    }
 
    cout << ret;
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>