[백준 / BOJ] C++ 27498 연애 혁명

27498번: 연애 혁명

 

문제

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

27498번: 연애 혁명

 

 

풀이

이미 성사된 사랑 관계는 포기하도록 하지 않아야 하기 때문에 반드시 포함되는 간선이 있어야 한다. 그리고 사랑 관계가 K 각 관계를 이루지 않아야 하므로 사이클이 없다(트리). 즉, 반드시 포함되어야 하는 간선이 있는 최소 스패닝 트리(MST)를 구현하는 문제다. 이 문제에선 포기하도록 만든 애정도의 합이 최소가 되어야 하므로 최대 스패닝 트리를 구하고 가중치의 합을 모든 간선의 가중치의 합에서 빼주면 된다.

 

반드시 포함되어야 하는 간선은 간선의 가중치의 최댓값이 10,000이므로 가중치에 10,000을 더해주면 반드시 포함되게 된다. 반드시 포함되어야 하는 간선의 개수를 세어 (개수 × 10,000)을 뺀 값이 최대 스패닝 트리의 가중치의 합이다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>

int V, E, sum = 0, cnt = 0;
vector<pii> graph[10001];

// 프림 알고리즘을 사용한 MST
int prim() {
  priority_queue<pii> pq;
  vector<int> visited(V + 1, 0);
  visited[1] = 1;
  for (pii edge : graph[1])
    pq.push(edge);
  int cost = 0;
  while (!pq.empty()) {
    int weight = pq.top().first;
    int node = pq.top().second;
    pq.pop();
    // 아직 연결되지 않았다면
    if (!visited[node]) {
      visited[node] = 1;
      cost += weight;
      // 다음 간선들 추가
      for (pii next : graph[node])
        if (!visited[next.second])
          pq.push(next);
    }
  }
  // 반드시 포함되어야 하는(이미 성사된) 간선의 수만큼 빼기
  return cost - cnt * 10000;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> V >> E;
  while (E--) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    sum += c; // 모든 간선의 가중치의 합
    // 이미 성사된 사랑 관계인 경우
    if (d == 1) {
      c += 10000; // 가중치 +10,000
      cnt++; // 이미 성사된 사랑 관계의 수
    }
    graph[a].push_back({c, b});
    graph[b].push_back({c, a});
  }
  cout << sum - prim();
  return 0;
}