[일반] 20390 완전그래프의 최소 스패닝 트리 시간줄이기

[익명(210.218)]

http://boj.kr/c111ffc08692410b91bdf20ea084094e

프림을 썼고, 메모리 초과가 나서 pq 대신에 multiset을 써서 수시로 필요없어진 값(간선정보)들을 지워줬고 붙어있는 점 탐색할 때도 set를 써서 tree의 구성원이 안 된 점을 담아서 tree에 포함되면 하나씩 없애주는 식으로 했습니다. 곱셈은 분할정복으로 log(숫자)만에 하도록 했는데 어떻게 하면 시간을 더 줄일 수 있을까요?

[pspspsps(182.231)]

프림에 멀티셋을쓰면 크루스칼이랑 시간복잡도가 달라지지가 않잖음 프림을 더 이해하셔야될듯 - dc App

[익명(210.218)]

아 이 문제에서는 ElogV가 n^2logn이 되버리고 V^2+E로 하면 n^2이 나오네요. 시간 줄이려면 정렬해야 한다는 편견이 있었던 것 같아요 ㅎ

[익명(210.218)]

생각해보니까 다익스트라에서도 E크기에 따라 둘 중에 골라서 사용해도 되겠네요