tlwpdus   1년 전

그래프 문제는 너무 어려워서... 한 달 째 고민하고 있는데 답이 안 나오네요 힌트 좀 주세요 ㅠㅠ


아 혹시 이것도 푸실 수 있으시면 이것도 힌트 주시면 감사하겠습니다... 이건 꼭 안 알려 주셔도 괜찮아요

트리 분할 - http://www.acmicpc.net/problem/2584

appa   1년 전

d(i, j) : i번째 도시까지 가는데 j개의 도로를 포장했을 때 이르는 최단거리.

O(E log E) 다익스트라 돌 듯이 해주면 됩니다.

트리 분할 문제는 트리 말단 노드에서부터 올라오면서 d(i, j) : i번 노드를 포함하는 부트리에서 j개의 정점을 선택할 때 생기는 간선 가중치의 합의 최솟값이라고 접근하면 됬던 것 같습니다. 답은 d(루트 노드, K)가 되겠군요. 대회 당시에는 만점자가 없었던(?) 걸로 기억하는데 옛날 ko4u 사이트에 이후연(ltdtl)님이 깔끔한 정해를 써주셨는데 지금은 사이트가 폭파되어서 사라졌네요...

tlwpdus   1년 전

오호라... 그렇군요 감사합니다 ㅎㅎ 그런데 도로포장 문제에서 K번 다익스트라를 돌아주는 방식인 건가요? 진짜 그래프는 잘 모르겠어서... 도로포장 조금만 더 자세히 설명해주시면 안 될까요?

appa   1년 전

보통 저는 우선순위큐로 새로 봐야할 정점이 없을 때까지 돌리는데.. 음..

큐의 원소로 x(a, b) = (정점, 포장한 도로 개수)라고 두면 됩니다.

while (Q에 원소가 있을 동안) {

1) 연결된 간선들 보면서 그냥 건너갈 때

2) 포장한 도로 개수가 K보다 작아서 새로 포장할 수 있을 때

}

이렇게 짜면 됩니당.

댓글을 작성하려면 로그인해야 합니다.