adxx   3년 전

안녕하세요 맞왜틀 질문글이라 죄송합니다.

게시판에 있는 테케와 인터넷서칭으로 찾을 수 있는 테케 모두를 통과하는 코드이지만 WA를 받았고, 어떤 경우를 커버하지 못하는지 도무지 짐잣이 안되어 이렇게 글을 남깁니다.

다른 여느 풀이처럼 크루스칼에 유니온파인드를 이용하여 MST를 찾아주었고, 이때 MST에 포함되는 간선들은 present라는 배열에 따로 기록했습니다.

또한 MST를 찾아주면서 MST에 포함되는 간선으로만 구성된 그래프2를 따로 만들어 두었습니다.(이를 이용해 dfs를 돌아 조상노드를 찾아줍니다)

이후 MST에 포함되는 간선의 갯수를 이용하여 첫번째 MST를 만들 수 있는지 없는지를 확인했습니다.

마지막으로 간선들을 처음부터 끝까지 보면서 MST에 포함되지 않는 간선 중 간선의 두 정점 사이의 최대값을 찾아주었습니다.(최대값은 새로 대체하려는 간선과 가중치가 같지 않게 처리했고 같다면 두번재로 큰 가중치를 대신 가져왔습니다)

이때 LCA를 활용하여 제거해야할 기존의 간선을 미리 구해뒀는데 이는 회소배열을 통해 구현했습니다.

즉 ld[I][j] := i의 2j번째 조상까지 가는 경로 중 {가장 큰 가중치, 2번재로 큰 가중치}

ld 배열은 dfs를 돌면서 조상노드를 찾아 줄때, 모든 i에대해 ld[i][0]=0으로 초기화시켰습니다.

코드도 너무 길고 정신없지만 정중히 부탁드리겠습니다.🙇🏻‍♂️

slah007   3년 전

77~90 LCA를 구하는 과정이 실제 LCA를 구하지 못하고 있습니다. diff의 각각의 bit가 1인지를 윗자리부터 봐야 하며 1이 아닌 i와 & 연산을 하면 전혀 다른 결과가 나옵니다.

input

8 8
1 2 7
2 3 6
3 4 5
4 5 4
5 6 3
6 7 2
7 8 1
1 7 99

answer: 121 (2 3 6 제외)

output: 120 (1 2 7 제외)

slah007   3년 전

아 죄송한데 생각을 잘못해서 반례는 제가 틀렸네요 아무튼 LCA쪽이 이상하긴 합니다

adxx   3년 전

덕분에 LCA에서 오타난 부분을 발견해서 AC를 받을 수 있었습니다.

첫 다이아 문제였는데 큰 도움 주셔서 정말 감사드립니다.🙇🏻‍♂️🙇🏻‍♂️🙇🏻‍♂️🙇🏻‍♂️

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