백준 알고리즘 6497번 : 전력난

링크

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

문제

성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들어가는데, 일부를 소등하여 그만큼의 돈을 절약할 수 있다.

그러나 만약 어떤 두 집을 왕래할 때, 불이 켜져 있지 않은 길을 반드시 지나야 한다면 위험하다. 그래서 도시에 있는 모든 두 집 쌍에 대해, 불이 켜진 길만으로 서로를 왕래할 수 있어야 한다.

위 조건을 지키면서 절약할 수 있는 최대 액수를 구하시오.

입력

입력은 여러 개의 테스트 케이스로 구분되어 있다.

각 테스트 케이스의 첫째 줄에는 집의 수 m과 길의 수 n이 주어진다. (1 ≤ m ≤ 200000, m-1 ≤ n ≤ 200000)

이어서 n개의 줄에 각 길에 대한 정보 x, y, z가 주어지는데, 이는 x번 집과 y번 집 사이에 양방향 도로가 있으며 그 거리가 z미터라는 뜻이다. (0 ≤ x, y < m, x ≠ y)

도시는 항상 연결 그래프의 형태이고(즉, 어떤 두 집을 골라도 서로 왕래할 수 있는 경로가 있다), 도시상의 모든 길의 거리 합은 231미터보다 작다.

입력의 끝에서는 첫 줄에 0이 2개 주어진다.

출력

각 테스트 케이스마다 한 줄에 걸쳐 절약할 수 있는 최대 비용을 출력한다.

예제 입력 및 출력

풀이법

그래프 상의 모든 간선의 가중치를 전부 구한다음, MST에 해당하는 간선들의 가중치만 빼주면 된다.

풀이 코드(C++)

#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define MAX 200001
#define INF 1e9+7
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using dbl = double;
using ldb = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
#define sz(a) int((a).size())

int root[MAX];

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

bool Union(int x,int y){
  x = find(x), y = find(y);
  if(x == y) return false;
  root[x] = y;
  return true;
}

struct Edge{
  int u,v,w;
  Edge(): Edge(-1, -1, 0){}
  Edge(int u1,int v1, int w1): u(u1),v(v1),w(w1){}
  bool operator < (const Edge& O)const{ return w < O.w; }; // 오름차순 정렬
};

int main(){
  fastio;
  int n,m;
  while(cin >> n >> m && (n != 0 || m != 0)){
    if(n == 0) break;
    Edge e[MAX];
    for(int i = 0; i < n; i++) root[i] = i;
    int allCost = 0;
    for(int i = 0; i < m; i++){
      int a = 0,b = 0,c = 0; cin >> a >> b >> c;
      e[i] = Edge(a,b,c);
      allCost += c;
    }
    sort(e, e + m); // 간선을 가중치를 기준으로 오름차순 정렬
    // result : 가중치 합, cnt : 뽑은 간선의 수
    int result = 0, cnt = 0;
    for(int i = 0; i < m; i++){
      if(Union(e[i].u, e[i].v)){
        result += e[i].w;
        if(++cnt == n - 1) break; // n - 1개의 간선을 뽑으면 나감.(MST)의 조건
      }
    }
    cout << allCost-result << "\n";
  }
  return 0;
}