[백준 / BOJ] C++ 6497 전력난

6497번: 전력난

 

문제

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

6497번: 전력난

 

 

풀이

두 집 사이의 거리만큼의 비용이 드는 가로등이 있고 가로등 불이 켜져 있는 도로로만 이동 가능하도록 유지하면서 최소 비용이 들도록 불을 꺼야 하므로 전체 간선의 가중치에서 최소 스패닝 트리(MST)의 가중치를 빼주면 된다.

 

 

코드

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

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);
  while (1) {
    int V, E, ans = 0, sum = 0;
    vector<pair<int, pair<int, int>>> edge;
    cin >> V >> E;
    if (!(V + E))
      break;
    p.resize(V + 1);
    iota(p.begin(), p.end(), 0);
    while (E--) {
      int u, v, w;
      cin >> u >> v >> w;
      edge.push_back({w, {u, v}});
      sum += w;
    }
    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 << sum - ans << '\n';
  }
  return 0;
}