가중치가 같은 엣지들을 한번에 묶어서 처리하는게 어떨까 합니다.
가중치가 같은 엣지들 K개를 한번에 처리한다고 생각해 보면, 그 엣지들을 연결할 때 영향을 받는 정점들은 최대 2*K개일 것입니다.
그리고, 각각의 간선에 심어지는 나무의 개수는 해당 간선의 아래쪽에 있는 정점 개수의 합 * 위쪽에 있는 정점 개수의 합 * 2가 되겠네요.
이것을 계산하기 위해서는 그 간선들과 간선에 달린 정점들로만 이루어진 트리를 새로 구축하면 O(K)에 계산할 수 있을 것 같습니다.
코딩은 약간 귀찮아 보이지만, 이런 식으로 생각해 보시면 해결할 수 있을 것 같네요.
smu201111192 7년 전
유니온 파인드 관련해서 문제를 하나 풀고 있는데요. 쉽지가 않네요.
바로 http://codeforces.com/contest/87/problem/D 이문제인데요.
문제를 간략히 요약하자면 이렇습니다.
트리형태의 마을이 있습니다.(가중치가 있는 트리)
모든 마을들은 다른 각 마을들과 전쟁을 한다고합니다. 즉 총전쟁횟수는 n*(n-1)번입니다.
어떤 u,v(u와 v는 서로 다른마을)마을이 전쟁을 하게 되면
u-v마을 사이를 이어주는 엣지들중에 가장 거리가 먼 (가중치가 가장 큰 ) 엣지에 나무를 하나 심는다고 합니다.
모든 마을 사이의 전쟁이 모두 끝나고 제일 많이 심어진 나무의 개수와 도로를 출력하는게 문제인데요.
처음에는 너무 쉽게 생각했습니다. 크루스칼 알고리즘 돌리듯이 가중치가 낮은 엣지 순서대로 정렬을 한후
매번 u-v를 있는 간선을 붙일 때 유니온 파인드 자료구조를 통해서 size[root(u)]*size[root(v)]*2 연산을 계속 수행하면서
답을 갱신해줬습니다. 네 바로 wa 받았습니다. 같은 가중치를 가진 엣지들도 존재더라고요...
가중치가 같은 엣지들은 어떻게 처리를 해줘야될까요?
에디토리얼도 보고 다른분들 코드도 봤지만 이해가 잘 가지 않아 질문남겨요...ㅠㅠ