[백준 / BOJ] C++ 1368 물대기

1368번: 물대기

 

문제

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

1368번: 물대기

 

 

풀이

최소 스패닝 트리(MST) 응용문제로 물을 끌어오는 비용과 우물을 파는 비용을 비교해야 한다. 따라서 가상의 정점을 만들고 i번째 우물을 파는 비용을 가상의 정점과 i번째 정점을 잇는 간선으로 추가해 주면 된다. 그리고 인접 행렬에서 각 정점 간 물을 끌어오는 비용을 간선으로 추가한다. 이제 크루스칼 알고리즘을 사용해 최소 스패닝 트리의 가중치를 구해주면 된다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int N, ans = 0;
vector<pair<int, pair<int, int>>> edge;
vector<int> p;

int find(int x) {
  if (p[x] != x)
    p[x] = find(p[x]);
  return p[x];
}

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> N;
  p.resize(N + 1);
  iota(p.begin(), p.end(), 0);
  for (int i = 1; i <= N; i++) {
    int x;
    cin >> x;
    edge.push_back({x, {0, i}});
  }
  for (int i = 1; i <= N; i++)
    for (int j = 1; j <= N; j++) {
      int x;
      cin >> x;
      edge.push_back({x, {i, j}});
    }
  sort(edge.begin(), edge.end());
  for (auto [weight, path] : edge)
    if (find(path.first) != find(path.second)) {
      ans += weight;
      merge(path.first, path.second);
    }
  cout << ans;
  return 0;
}