(6497) 전력난

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

단계별로 풀어보기

35단계(최소 신장 트리) 5번째

 

 

 

스패닝 트리를 만들 수 있는 만큼의 불은 켜둬야 한다. 이때 절약하는 돈은 입력받은 거리 총합-스패닝 트리 비용이므로, 이 값을 최대로 만들기 위해서는 스패닝 트리를 최소로, 즉 최소 신장 트리를 만들어야 한다.

 

 

 

#include <iostream>
#include <queue>
using namespace std;
typedef pair<int, int> p;

int solve(int m, int n){
  vector adj(m, vector<p> ());
  vector<bool> visited(m);
  priority_queue<p, vector<p>, greater<p>> pq;
  int s= 0;
  
  while(n--){
    int x, y, z;
    
    cin >> x >> y >> z;
    
    s+= z;
    adj[x].push_back({z,y});
    adj[y].push_back({z,x});
  }
  
  visited[0]= true;
  for(p edge:adj[0])  pq.push(edge);
  
  int cnt= 1, cost= 0;
  
  while(!pq.empty()){
    p now= pq.top();
    pq.pop();
    
    if(visited[now.second])  continue;
    
    visited[now.second]= true;
    cnt++;
    cost+= now.first;
    
    if(cnt==m)  break;
    
    for(p next:adj[now.second]){
      if(visited[next.second])  continue;
      
      pq.push({next.first, next.second});
    }
  }
  
  return s-cost;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  while(true){
    int m, n;
    
    cin >> m >> n;
    
    if(!m)  break;
    
    cout << solve(m, n) << "\n";
  }
  
  return 0;
}