Yukicoder No. 114 遠い未来

Yukicoder No. 114 먼 미래

문제 링크

문제

SRM 10000이 열린 것도 옛날이야기.

여기서는 대회의 Div2 Easy 문제를 소개하려고 한다.

 

문제

간단히 말하면, 방향이 없고 가중치가 붙어있는 그래프가 주어진다.

정점 중 몇 개는 "중요"한 점이다.

모든 중요한 점을 연결하는 부분 그래프 중 간선 가중치 합이 최소가 되는 것을 구하고 싶다(이 그래프는 트리이다).

그때의 가중치 합을 출력하는 문제.

입력

자세한 입력 형식은, 원문을 확인해주세요.

입력의 1번째 줄에는 정점 수 $N$, 간선 수 $M$, 중요한 정점 수 $T$가 주어지고,

다음 $M$ 개의 줄에 $3$개의 정수 $a_i$, $b_i$, $c_i$가 정점 $a_i$와 정점 $b_i$를 가중치 $c_i$로 잇는다는 의미로 주어진다.

마지막 $T$ 개의 줄에는, 중요한 정점이 적혀있다.

$1 \le N \le 35$

$N-1 \le M \le \frac{N(N-1)}{2}$

$1 \le T \le N$

$1 \le a_i, b_i, v_i \le N$

$1 \le c_i \le 100$

$i \ne j \Leftrightarrow v_i \ne v_j$

 

입력으로 주어지는 그래프는 연결 그래프이고, 다중 간선이나 루프가 없습니다.

출력

첫 번째 줄에 답을 출력해 주세요. 개행 문자를 넣을 것.

 

프로덕션에서는 해당 라이브러리를 사용했습니다.

http://www.prefield.com/algorithm/dp/steiner_tree.html (일본어, 링크 잘림, web archive)

(역자 주: 해당 링크는 풀이의 큰 스포일러가 들어 있습니다.)

풀이

힌트 1

이 문제는 Steiner Tree라고 불리는 유명한 문제이고, NP-Complete 문제입니다

 

$K$가 작을 때와 클 때를 나눠서 풀어봅시다. 시간 복잡도는 두 풀이의 최솟값입니다.

각각을 힌트 2/풀이 1, 힌트 3/풀이 2라고 적겠습니다. 문제의 링크에는 풀이 1에 대한 설명이 적혀있습니다.

 

코드 링크를 우선 힌트에 작성하도록 하겠습니다. (시간제한이 여유롭지 못해, C++을 사용했습니다.)

코드: https://yukicoder.me/submissions/736255

힌트 2

Steiner Tree의 구조를 생각해봅시다. Steiner Tree의 구조는 어떠할까요? Tree-DP를 사용할 수 있을까요?

힌트 3

Minimum Spanning Tree는 일반적으로 쉽게 해결할 수 있는 문제입니다.

풀이 1

$K$가 작을 때

시간 복잡도 $O(NM + 3^T N + 2^T N^2)$에 해결하는 풀이입니다.

이 방법을 Dreyfus-Wagner법이라고 한다고 합니다.

 

Steiner Tree가 존재한다고 생각해 봅시다. Steiner Tree의 어떤 간선 $p-q$를 잡아서 해당 간선을 끊으면, 왼쪽은 중요한 정점의 부분집합 $A$와 $p$가 포함된 Steiner Tree, 오른쪽은 중요한 정점의 부분집합 $B$와 $q$가 포함된 Steiner Tree가 됩니다. 이는 중요한 정점의 부분집합 $A \cup B$와 정점 $p, q$를 포함한 Steiner Tree입니다.

모든 Steiner Tree는 이 방식으로 만들 수 있기 때문에, 우리는 중요한 정점의 부분집합 $S$와 어떤 정점 $p$를 포함하는 Steiner Tree의 최솟값을 다음과 같은 방식으로 구할 것입니다:

 

$D_{S, \ p}$를 $S \cup \{p\}$의 모든 정점을 포함하는 최소 크기의 Steiner Tree라고 합시다. 또한, $d(p\, q)$를 두 정점 $p$, $q$ 사이의 거리라고 합시다.

 

Base case: $|S| = \{q\}$ 인 경우, $D_{S, \ p} = d(p, q)$

Inductive case: $D_{S, \ p} = \min_{A \cup B = S,\ q \in V} \left(D_{A, \ p} + D_{B, \ q} + dist(p,\ q)\right)$ 가 됩니다.

 

Inductive Case를 계산하는 시간 복잡도가 $O(3^T N^2)$이 됩니다. (모든 부분집합에 대해서, 해당 집합의 부분집합을 순회하는 시간 복잡도는 $O(3^N)$입니다.) 우리는 한 가지의 트릭을 사용해서 시간 복잡도를 줄일 것입니다.

간선을 기준으로 끊는다고 생각하지 않고, 정점을 기준으로 끊는다고 생각하면, 모든 간선에 대해 계산할 필요 없이, 정점에 대해서만 계산을 하면 되기 때문에, 시간 복잡도를 $O(N)$ 만큼 줄일 수 있습니다.

 

여기서, 간선을 새로 추가하는 방법은, $S \cup \{q\}$의 Steiner Tree를 $S \cup \{p\}$의 Steiner Tree에 $p$부터 $q$까지의 경로를 이어준 것이라고 생각하면 됩니다.

 

Inductive Case 1: $D_{S, \ p} = \min_{A \cup B = S,\ q \in V} \left(D_{A, \ p} + D_{B, \ p}\right)$

Inductive Case 2: $D_{S, \ p} = \min_{q \in V} \left( D_{S, \ q} + d(p,\ q) \right)$

이 두 가지로 Steiner Tree를 만들 수 있으며, 모든 집합마다 1, 2를 차례대로 계산해주면, 빠뜨리지 않고 모두 계산할 수 있습니다.

풀이 2

시간 복잡도 $O(M \log M + 2^{N-T} M \alpha(M, N))$에 해결하는 풀이입니다.

 

$T$ 개의 정점을 모두 포함하는, $N$ 개 정점의 부분집합으로 가능한 것은 $2^{T-N}$ 개가 있습니다. 해당 정점 집합에 대해서, Minimum Spanning Tree문제를 해결해서 최솟값을 구하면, 그것이 답이 됩니다.