9개의 댓글이 있습니다.
-
-
TurtleShip -
올바른 사이클 디텍션 방법이 궁금합니다. 제가 사용한 방법이 틀렸다는 것은 알고있습니다.
제가 사용한 방법이 Being님이 말씀하신 방법과 (가중치가 같은 엣지들끼리 묶어서 처리) 비슷합니다. 그리고 현재 곤란을 겪고 있는 부분이 must와 at least one을 분간하는 방법입니다.
브릿지가 존재하면 must이고 아니면 at least one이 된다는 것은 알고 있습니다 ( cut property). 문제는 코딩을 할 때 어떻게 해야 (어느 자료 구조나 알고리즘을 사용해야 되는지)할 지를 모르겠습니다.
bulk를 찾는 것은( 인덱스 i 와 j 를 사용) 하였으나, 어떻게 해야 bridge를 구별할 수 있느지 모르겠어요..;;제가 쓴 글에 예제를 올려놨는데 지금 보니까 문장 구분이 제대로 안 되있네요. 혹시 제가 must 랑 at least one 에 곤란을 겪는다는 것이 이해가 잘 안 되시면 제 예제를 다시 봐주세요. 지금 수정할 꼐요 ^^
12년 전 link
-
-
-
TurtleShip -
아,, 감사합니다 ^^
bulk만들어서, 그 bulk가 MST에 포함되어있는지 확인한 후,
yes 일 경우 일단 모든 bulk안 모든 edge를 at least one으로 마킹.
그 다음 bulk안에서 bridge detection을 돌려서 해당 edge bridge일 경우 must로 마킹.혹시 bridge detection을 코딩할 수 있는 방법이 설명되어있는 싸이트 링크 가 있으신가요? bridge detection이 무엇인지는 아는데 직접 코딩 해본적이 없어서 조금 막막해서요.
빠르고 친절한 답변 감사합니다 ^^
12년 전 link
-
-
-
hyunhwan -
TurtleShip / 이것 한번 참고해보세요.
http://www.cs.cornell.edu/~wdtseng/icpc/notes/graph_part1.pdf
12년 전 link
-
-
-
TurtleShip -
LIBe님 좋은 링크 감사합니다. 제가 찾던게 그거 였습니다. 저희 학교자료인데 제가 못 찾았네요 ..;;;;
Being님 좋은 조언 감사드립니다 ^^
12년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
TurtleShip
안녕하세요,
어제 열였던 codeforces Round #111에 나왔던 문제 D (Edges in MST) 인데요,
알고리즘 구상까지는 했는데 implementation 하려니까 자꾸 꼬여서 제 접근방법을 어떻게 고쳐야 되는지 궁금해서 글을 올립니다 (인터넷 검색하다가 여기로 오게 되었네요. 좋은 싸이트인거 같습니다 ^^)
문제의 내용은 대략 아래와 같아요.
undirected weight graph가 주어졌을 때, 각 edges들을 다음 3가지중 하나로 분류하라.
1) MST에 속하지 않는다
2) 모든 MST에 속한다.
3) 적어도 한 개의 MST에 속한다.
input으로는 각 edges의 정보가 주어져요 (연결하는 노드 2개와 weight).
정보자체가 edge에 관해서 주어졌으니 Prim Algorithm보다 Kruskal Algorithm이 적합한 거 같았고, 2번과 3번 경우를 분류하기 위해서는 cycle property를 써야 할 거 같아요.
Kruskal Algorithm => Edge가 MST에 속하는지 속하지 않는지 알려준다.
Cycle Property => 모든 MST에 속하는지 그렇지 않은지 알려준다.
현재 제가 쓰고 있는 접근 방법은
모든 edge를 weight에 관하여 오름차순으로 정리한다.
while(정리한 edge를 처음부터 시작하여 끝까지 도달하거나 모든 노드를 연결했을 때 종료)
{
현재 i 번째 edge에 있다.
j=i부터 시작하여, j번째 edge가 i 번째 edge와 다른 weight를 가질 때 까지 j를 증가시킨다.
현재 MST정보를 temp에 저장한다.
[i, j) 사이에 있는 edge가 cycle를 이루는 지 그렇지 않은지 확인하면서 MST에 포함시킨다. 만약에 현재 확인하고 있는 edge가 cycle를 이루게 하고, 그 이유가 자신과 같은 cost를 가진 edge 때문이라면 (temp에서도 현재 edge를 추가시켰을 때 cycle을 이루는지 안 이루는지 확인해서) i부터 현재 edge 사이에 있는 모든 edge를 3번 경우에 포함시킨다.
}
위와 같은 접근 방법을 쓰면, 다음과 같은 문제점이 발생합니다.
edge의 정보를 다음과 같이 표현하고 ( node A, node B, weight C) ,
아래와 같은 경우가 있을 때
edge 1 : (A,B, 2)
edge 2 : (B,C, 2)
edge 3 : (C, D, 2)
edge 4 : (C,A, 2)
정답은
edge 1 : 적어도 한 개의 MST에 속한다.
edge 2 : 적어도 한 개의 MST에 속한다.
edge 3 : 모든 MST에 속한다.
edge 4 : 적어도 한 개의 MST에 속한다.
하지만 저의 접근방법은 다음과 같이 출력합니다.
edge 1 : 적어도 한 개의 MST에 속한다.
edge 2 : 적어도 한 개의 MST에 속한다.
edge 3 : 적어도 한 개의 MST에 속한다.
edge 4 : 적어도 한 개의 MST에 속한다.
제 cycle detection 방법이 잘못됬다는 건 알겠는데, 어떻게 고쳐야 할지를 모르겠네요. 혹시 codeforces #111 round에 참가하셨거나, 위의 문제를 어떻게 풀어야 할지 아시는 분은 답변 부탁드려요 ^^:;;
codeforces 채점방법은 AOJ와 똑같으나, 왜 틀렸는지 test case를 공개해준다는 점에서는 어쩌면 더 낫다고 볼수도 있어요.
그리고 혹시 codeforces나 TopCoder 하시는 분 게시면 정보나 의견 교환 하게 연락 부탁드려요. 제 iChat , google Chat, e-mail 은 sk765@cornell.edu 이고
알고리즘 대회 아이디는 TurtleShip 으로 쓰고 있어요.
좋은 하루 되세요 ^^
12년 전