주어진 그래프 G의 최소 스패닝 트리 T (n은 정점 및 m 에지)와 새 에지 e = (u, v)를 G에 더한다. 그래프 G + e의 최소 스패닝 트리를 찾는 효율적인 알고리즘을 제공한다. 알고리즘은 전체 크레딧을 받으려면 O (n) 시간에 실행해야합니다. Skiena 설명서에서O (n)에서 새 스패닝 트리를 찾고
(C)
시작 프림 또는 ALG U 또는 V에서 크루스 칼 우리가 주어진 스패닝 트리 경로의 조각에 도달 할 때까지? 새로운 스패닝 트리가 하나의 새로운 에지에서 많이 바뀌지는 않을 것 같습니다.
G에서 새 모서리의 끝점 사이의 경로를 결정합니다. 해당 경로의 최대 길이 가장자리가 새 모서리보다 큰 경우 새 모서리로 바꾸십시오. 이것은 O (N) 시간에 실행됩니다.
출처 :이 이후 Trail Maintenance IOI 2003
숙제가 아닌 질문에 대한 완벽한 답. 하지만 그것은 숙제 문제입니다. -1. –
@j_random_hacker - 왜 사람들은 당신이 왜 downvoted인지 궁금합니다. [Meta에 관한이 질문] (http://meta.stackexchange.com/questions/76694)을보십시오. 마코 그 (marcog)는 숙제에 대한 더 나은 대답을하기 위해 무엇을 말해야합니까? – ChrisW
와우! 나는 많은 논란을 불러 일으키 리라 기대하지 않았다. 포인터에 대한 @ChrisW 감사합니다. 나는 그 메타 질문에 대한 나의 입장을 설명하려고 노력할 것이다. (나는 메타 질문의 훌륭한 예라고 생각한다.) –
이 숙제 문제, 당신은 더 구체적으로 당신이 도움이하고 싶은 것을 설명 할 수 있습니까? 이것은 큰 문제이지만, 우리는 단지 당신에게 답을 줄 뿐만이 아닙니다. – templatetypedef