[BOJ 5477] Training

문제: https://www.acmicpc.net/problem/5477

 

풀이:

전반

우선, 무조건 제거되어야 하는 간선들을 찾아줍니다. 간선 $(u, v, w)$에 대해 트리에서 $u \rightarrow v$ 경로의 길이가 홀수이면, $(u, v, w)$와 트리 경로만 이용해서 짝수 사이클을 만들 수 있습니다. 그렇기 때문에 무조건 삭제되어야 합니다.

 

이제, 짝수 사이클이 만들어지는 조건을 찾아봅시다.

$(u_1, v_1, w_1)$ 간선이 트리를 통해 만드는 사이클과, $(u_2, v_2, w_2)$ 간선이 트리를 통해 만드는 사이클은 모두 홀수 사이클입니다. 이제 두 사이클을 XOR하면 (즉, 간선 중 둘 중 한 쪽에만 포함된 간선을 찾아서 새로운 그래프를 만들면), 새로운 그래프는 사이클 2개로 이루어져있거나, 1개로 이루어져있습니다. 두 사이클에서 겹치는 간선이 있으면, 두 사이클이 하나로 합쳐져서 하나의 사이클을 만듭니다. 이 때 사이클에 포함된 간선의 개수는 짝수이므로, 둘 모두를 선택하는 것이 불가능합니다.

만약에 이런 간선 쌍을 하나도 선택하지 않았다면, 어떤 간선은 최대 하나의 사이클에만 포함됩니다(즉, 선인장 그래프가 됩니다.), 그러므로 문제는 트리에서 경로와 가중치가 주어졌을 때, 서로 서로소인 경로를 골라서 합을 최대화하는게 목적이 됩니다. (이 경로만 살리고, 나머지 경로를 모두 파괴합니다)

후반

트리에서 해결하는 문제이므로, 일반적인 트리 분할정복을 생각해 보려고 하지만, 루트를 거쳐가는 간선을 선택해야해서 잘 처리가 되지 않습니다. 트리 분할정복을 확장하여 다음과 같은 아이디어를 생각해봅시다.

• $D(a, f)$: $a$를 루트로하는 서브트리에서, $a-f$ 간선과 겹치지 않는 경로를 이용해서 서로소인 경로의 합의 최댓값

이 경우, 각 서브트리에서 얻을 수 있는 이득으로는 다음과 같은 식이 세워지게 됩니다.

• $a$의 자식 $c$중 $c$를 루트로 하는 서브트리에서 $f$가 없는 경우
  • $c$ 서브트리만 이용해서 얻을 수 있는 가중치 합이 $D(c, \textrm{None})$ 입니다.
• $a$의 자식 $c$중 $c$를 루트로 하는 서브트리에서 $f$가 있는 경우
  • $c$ 서브트리만 이용해서 얻을 수 있는 가중치 합이 $D(c, f)$ 입니다.
• $a$에서 시작해서 자손으로 가는 경로 $(a, u, w)$가 있는 경우
  
  •  $u$를 포함하는 서브트리를 가진 자식이 $c$라고 하면, $c$ 서브트리만 이용해서 얻을 수 있는 가중치 합이 $D(c, u) + w$입니다.
• $a$를 가장 높은 지점으로 거치는 경로 $(u, v, w)$ (즉 $LCA(u, v) = a$인 경로) 가 있는 경우
  • $u, v$를 포함하는 서브트리를 가진 자식이 각각 $c, d$라고 하면, $c$와 $d$ 서브트리를 이용해서 얻을 수 있는 가중치 합은 $D(c, u) + D(d, v) + w$ 입니다.

정점 $a$에서 자식들을 적당히 이용하여 가중치 합을 최대화 하는 문제로 바뀌게 됩니다. 이 문제는 가중치가 있는 최대 매칭 문제로 풀 수 있으며, bit-DP를 이용하면 $O(n \cdot 2^n)$ 시간에 풀 수도 있고, $O(n^3)$ 시간에도 풀 수 있습니다. (문제에서는 간선의 차수가 $10$ 이하이고, $O(n \cdot 2^n)$ 알고리즘으로 충분합니다.)

 

가능한 모든 $(a, f)$ 쌍에 대해서 문제를 풀어주면 시간복잡도는 $O((N+M) \sum_{u \in V} \mathbb M (\mathrm{deg}(u)))$ 정도가 됩니다. $\mathbb M (n)$ 은 매칭의 시간복잡도로, $O(n \cdot 2^n)$ 으로 구현하면 됩니다.

 

코드: https://www.acmicpc.net/source/share/9f33093e21f147aa9a6b972868d5e278