유니온 파인드 관련해서 문제를 하나 풀고 있는데요. 쉽지가 않네요.

바로 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 받았습니다. 같은 가중치를 가진 엣지들도 존재더라고요...

가중치가 같은 엣지들은 어떻게 처리를 해줘야될까요?

에디토리얼도 보고 다른분들 코드도 봤지만 이해가 잘 가지 않아 질문남겨요...ㅠㅠ


dotorya   3달 전

가중치가 같은 엣지들을 한번에 묶어서 처리하는게 어떨까 합니다.

가중치가 같은 엣지들 K개를 한번에 처리한다고 생각해 보면, 그 엣지들을 연결할 때 영향을 받는 정점들은 최대 2*K개일 것입니다.

그리고, 각각의 간선에 심어지는 나무의 개수는 해당 간선의 아래쪽에 있는 정점 개수의 합 * 위쪽에 있는 정점 개수의 합 * 2가 되겠네요.

이것을 계산하기 위해서는 그 간선들과 간선에 달린 정점들로만 이루어진 트리를 새로 구축하면 O(K)에 계산할 수 있을 것 같습니다.

코딩은 약간 귀찮아 보이지만, 이런 식으로 생각해 보시면 해결할 수 있을 것 같네요.

네 그런식으로 방향을 잡고 코딩을 하고 있는데 문제가 하나 더 발생했습니다. ㅠㅠ

(size[특정간선을 모두 처리했을때의 해당 집합의 크기]-size[root[u]]) * size[root[u]]*2라는 식을 세웠습니다.->(해당간선의 위쪽간선의 합*아래쪽 간선의합)

그런데 u라는점이 위쪽에 달린정점인지 아래쪽에 달린 정점인지를 파악하기가 힘든거 같습니다. 

이부분을 그냥 단순히 1번(또는 다른정점)정점에서 dfs를 돌려서 각정점에 depth 를 매겨주고 

그 depth 를 기준으로 아래 위 구분이 가능할까요?

즉 어떤 간선을 연결하는과정에서 u라는 버텍스를 포함하는 집합과 v라는 버텍스를 포함하는 집합을 연결하게되는데

u와 v의 아래 상하 관계를 알아야 

size[특정간선을 모두 처리했을때의 해당 집합의 크기]-size[root[v]]) * size[root[v]]*2 

size[특정간선을 모두 처리했을때의 해당 집합의 크기]-size[root[u]]) * size[root[u]]*2

매merge해주는 과정에서 위 두식중 어느식을 쓸지를 결정할 수 있을텐데 

그 방법을 모르겠습니다. 

dotorya   3달 전

상하 관계를 굳이 알 필요가 없지 않나요?

특정 간선을 기준으로 양쪽에 있는 정점의 개수만 계산할 수 있다면 충분할 것 같습니다.

이건 어떤 점을 루트로 잡고 계산하든 같은 값이니, 굳이 상하 관계를 따지지 않아도 계산할 수 있을 것 같습니다.

감사합니다. 다시 한번 생각해볼게요

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