acm을 준비하면서 모르는것만 쌓여가고 물어볼 곳은 마땅히 없고.. 해서 계속 이곳에 도움을 요청하게 되네요..ㅠㅠ
문제링크: D번 http://neerc.ifmo.ru/past/2007/northern/problems.pdf
해설:
n(<=1000)의 노드에 m(<=10000)개의 간선이 있는 weighted 양방향 그래프에서 mst를 구하려고 합니다. 단, 두 종류의 길이와 단위 코스트가 주어지는 막대가 주어집니다. 각 엣지를 두 종류중 하나로 바꿔야 하며, 두 종류를 잘라 합쳐서 한 엣지를 만드는 경우는 불가능 합니다. 가능한 spanning tree중 최소 코스트를 구하세요.
불가능한 경우도 존재합니다.
해를 구성하는 트리의 T의 형태가 mst가 아닐때,
어떤 e_i가 존재해서 T에 e_i를 추가하면, 생기는 사이클 중
가장 큰 edge를 e_j라 하면 Len(e_j)>Len(e_i)인 i j 조합쌍이
최소한 하나는 존재할 것인데, e_j를 구성했던 성분을 전부 e_i로 옮기면 항상 해가 더
좋아지므로 기본 구조로 mst를사용하지 않은 해는 항상
최적해가 아니다라고 말할수 있을거같은데요..
그리고 그것의 대우명제는 스포일러 1.이죵..
네.. 2번 질문을 정확히 쓰질 않았네요 엣지 번호의 구성이 동일할것이라는 가정이 아니라 엣지 길이들의 구성이 동일할 것이다라는 가정이었습니다. 크루스컬의 경우 어차피 소트해서 구해나가니 당연히 항상 같겠지만 프림으로 구해나가면 얼마든지 달라질수있을거라(?) 생각이 불현듯 들어서요 ㅠㅠ
아.. 생각해보니 크루스컬의 경우는 같은 엠에스티중 엣지가 가장 작은것들을 무조건 포함하면서 mst를 구성하므로 mst 알고리즘중 크루스컬만이 정해를 뱉어내겠네요 p5 p6로 나눌때 더 가격이 작은 놈이 최대가 구성이 되려면 엣지 길이가 작은놈들이 많을수록 유리하니까요. 라는 느낌이 또 드네요 ㅋ.ㅋ;
yeonzzg
acm을 준비하면서 모르는것만 쌓여가고 물어볼 곳은 마땅히 없고.. 해서 계속 이곳에 도움을 요청하게 되네요..ㅠㅠ
문제링크: D번
http://neerc.ifmo.ru/past/2007/northern/problems.pdf
해설:
n(<=1000)의 노드에 m(<=10000)개의 간선이 있는 weighted 양방향 그래프에서 mst를 구하려고 합니다. 단, 두 종류의 길이와 단위 코스트가 주어지는 막대가 주어집니다. 각 엣지를 두 종류중 하나로 바꿔야 하며, 두 종류를 잘라 합쳐서 한 엣지를 만드는 경우는 불가능 합니다. 가능한 spanning tree중 최소 코스트를 구하세요.
불가능한 경우도 존재합니다.
제한:
각 간선의 weight: 0<= l <= 100
종류1 막대의 길이: 1<= q5 <= 10000
종류1 막대의 단위코스트: 1<= p5 <= 10000
종류2 막대의 길이: 1<= q6 <= 10000
종류2 막대의 단위코스트: 1<= p6 <= 10000
억쎕을 받기는 했는데 단순히 직감과 가정만 가지고 풀어서 이렇게 질문드립니다. 가정을 2가지로 하고 풀었는데요,
라고 생각하고 크루스컬로 구한 mst의 엣지 가지고 냅색을 돌려 해를 찾았더니 억쏍이 뜨더라구요..
mst에 관한 아는건 그저 그리디한 성질을 만족한다 정도 뿐이라..ㅠ
저 2가지 가정이 항상 옳은건가요?.?
11년 전