백준 14950번 정복자[C++]

1. 문제 풀이

 안녕하세요 오늘 풀어본 문제는 백준 14950번 정복자입니다. 문제의 유형은 최소 신장 트리입니다. 그래프 이론 알고리즘은 문제의 설명을 읽으면서 어떤 그래프 형태인지 파악할 수 있어야 합니다. 이 문제의 경우, 무방향 가중치 연결 그래프임을 알 수 있습니다. 정복할 때마다 t만큼 모든 도로의 비용이 증가하지만 모든 도시를 정복해야 하므로 추가되는 비용은 정점의 개수에 따라 일정합니다. 따라서 최소 신장 트리가 되는 간선들의 가중치를 모두 더하고 정점의 개수에 맞추어 추가 비용을 더해주면 쉽게 구할 수 있습니다.

 

2. 코드 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

int n, m, t, u, v, w;
vti edges;

// disjoint-set
vi p(10005, -1);

int find(int x){
  return (p[x] < 0 ? x : p[x] = find(p[x]));
}

void merge(int x, int y){
  x = find(x);
  y = find(y);
  if(x == y) return;
  if(p[x] == p[y]) p[x]--;
  if(p[x] < p[y]) p[y] = x;
  else p[x] = y;
}

int main() {
  fastio(nullptr, false);
  cin >> n >> m >> t;
  while(m--){
    cin >> u >> v >> w;
    edges.pb({w, u, v});
  }
  sort(all(edges));
  ll ans{}, cnt{};
  for(auto &cur : edges){
    auto &[c, a, b] = cur;
    if(find(a) == find(b)) continue;
    merge(a, b);
    cnt++;
    ans += c;
    if(cnt == n-1) break;
  }
  cnt = (n < 3 ? 1 : (n-2) * (n-1) / 2);
  cout << ans + cnt * t; 
}

 

3. 제출 결과