(백준) 27498번 - 연애 혁명

문제

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

풀이

문제 조건은 총 세 가지이다.

사랑 관계 중, 이미 성사된 사랑 관계는 포기하도록 하지 않는다.

이는 해당 간선이 반드시 포함되어야 한다는 의미이다.

사랑 관계가 $K$각 관계를 이루지 않도록 한다. $K$$(K \geq 3)$각 관계라는 것은 임의의 서로 다른 K명의 학생 $A_1, A_2, \cdots, A_i, \cdots, A_K$에 대하여, $i \neq 1$인 모든 $i$에 대해서 $A_{i-1}$과 $A_{i}$사이에 사랑 관계가 존재하며, $A_K$와 $A_1$사이에 사랑 관계가 존재하는 것을 의미한다.

즉, 최종 그래프는 사이클이 존재하지 않는 트리 형태이다.

포기하도록 만들 수 있는 경우가 여러가지일 경우 포기하도록 만든 애정도의 합을 최소화한다.

트리를 구성하는 가중치의 합이 최대가 되어야 한다. 즉, 최대 스패닝 트리 문제이다.

---

일반적인 최소/최대 스패닝 문제와 동일하나, 특정 간선이 반드시 포함되어야 한다는 조건이 있다. MST에서 특정 간선이 반드시 뽑히게 하고 싶다면 해당 간선의 가중치를 조정하면 된다. 가령, 이 문제에서 가중치 값의 범위는 $1 \leq c_i \leq 10000$이므로, 반드시 뽑혀야 하는 간선의 가중치에 10000을 더하면 우선순위 큐에서 무조건 뽑힐 것이다.

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

typedef pair<int, int> pii;

int visited[10001];
vector<pii> graph[100001]; // { 노드, 가중치 }

int main() {
	int n, m;
	cin >> n >> m;

	int sum = 0; // 전체 가중치의 합, 이후 mst에서 sum을 빼면 포기한 간선의 가중치의 최솟값이 도출됨.
	int mst = 0; // MST를 이루는 간선의 가중치 합
	priority_queue<pii> pq;

	for (int i = 0; i < m; i++) {
		int a, b, w, f;
		cin >> a >> b >> w >> f;

		sum += w;

		// 끊어지면 안 되는 관계의 가중치에 최댓값을 더해 무조건 뽑히도록
		if (f == 1) {
			w += 1e4;
		}

		graph[a].push_back({ b,w });
		graph[b].push_back({ a,w });
	}

	pq.push({ 0,1 });

	while (!pq.empty()) {
		int w = pq.top().first;
		int node = pq.top().second;
		pq.pop();

		if (visited[node]) continue;

		visited[node] = 1;
		if (w > 1e4) w -= 1e4;
		mst += w;

		for (auto edge : graph[node]) {
			int nnode = edge.first;
			int nw = edge.second;

			if (!visited[nnode]) {
				pq.push({ nw,nnode });
			}
		}
	}

	cout << sum - mst;
}

시간복잡도

모든 간선에 대하여 힙 연산을 수행하므로 $O(MlogM)$ 또는 $O(MlogN)$이다.

공간복잡도

graph 는 $N$개의 정점에 대하여 $M$개의 간선을 양방향으로 저장하므로 $O(N+M)$, visited 는 모든 정점에 대하여 공간이 필요하므로 $O(N)$, pq는 최악의 경우 모든 간선이 들어갈 수 있으므로 $O(M)$이다. 따라서 전체 공간복잡도는 $O(N+M)$이다.