Problem Solving Diary #18
BOJ 15481. 그래프와 MST 일단 원래 그래프의 MST를 구한다. 그리고 각 간선에 대해, 해당 간선의 양끝점을 잇는 경로에서 가장 큰 가중치를 가지는 간선을 빼 주고 해당 간선을 넣으면 이것이 가장 싼 MST가 된다. 구현은 LCA와 sparse table을 잘 이용하면 HLD + segment tree 없이도 할 수 있다. 시간 복잡도는 $\mathcal{O}(M \log N)$이다. BOJ 30896. 두 팀으로 나누기 두 팀의 $\min(A_i)$와 $\sum B_i$를 각각 $a_1$과 $a_2$, $b_1$과 $b_2$라고 하자. $a_1$과 $a_2$ 중 하나는 $\min_{1 \le i \le N} A_i$이다. WLOG $a_1$이라고 하자. $a_2$를 정하는 방법은 최대 $10..
코딩/문제풀이
2024. 4. 6. 20:38