alohajm   8달 전

최소스패닝트리 문제중에 단순한 최소 스패닝트리 말고

각 간선을 포함하는 최소 스패닝트리나 포함하지 않는 최소 스패닝트리를 각 간선마다 비용을 모두 구하는 문제는 어떻게 풀어야 하나요...?

각 간선을 포함or배제시키고 스패닝 트리를 구하게 하면 N^2logN이 나오는데

당연히 N^2logN은 아니고 NlogN으로 나올거같은데...

문제 풀다보니까 이런거 비슷한게 많이 나오는데 할줄을 몰라서요 ㅠㅠㅠ

아니면 스패닝트리 관련된 사이트좀 알려주시면 감사하겠습니다 ㅠㅠ

koosaga   8달 전

스패닝트리 관련된 사이트가 특별히 있지는 않고요

말씀하시는 문제가 KOI 2014 고등부 4번인거 같은데, 제가 옛날에 풀이 슬라이드를 만들었었어요. 

http://codeup.kr/JudgeOnline/problem.php?id=4829

https://www.acmicpc.net/problem/10637

http://amugelab.tistory.com/entry/KOI-2014-%EC%95%...

alohajm   8달 전

감사합니다!!

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