문제는 https://www.acmicpc.net/problem/2649 이거고
논문은 forwarding이라는 기법을 사용하는데 이게 원본 그래프를 변형시켜버림, 그런데 문제에서는 최적해를 구성해야 해서 원본 그래프를 복원해야 하는데 그 방법이 너무 어려워서 잠시 그만두고 아예 새로운 방법으로 접근하고 있음
생각한 방법은 이런데 반례있을지 봐주시면 감사하겠음
1. Dfs 돌리면서 depth 구하고 그 과정에서 descendant 개수도 다 구함
2. 자식 노드들에게 하나하나 연락을 보내는데 descendant가 많은 놈부터 보냄. descendant 개수가 똑같은 경우 depth가 더 깊은 곳까지 가는 자식노드부터 보냄
3. 노드 각각의 도달 시간은 bfs로 계산하되 parent가 여러개인 경우가 있을수 있으니 중복 방문을 허용하고 최적해 갱신을 함
이게 아이디어인데 반례가 어떤게 잇을까요??
아직 제출은 안했고 생각나는 케이스 외에 랜덤케이스 만드는 코드 짜고있어요
논문은 forwarding이라는 기법을 사용하는데 이게 원본 그래프를 변형시켜버림, 그런데 문제에서는 최적해를 구성해야 해서 원본 그래프를 복원해야 하는데 그 방법이 너무 어려워서 잠시 그만두고 아예 새로운 방법으로 접근하고 있음
생각한 방법은 이런데 반례있을지 봐주시면 감사하겠음
1. Dfs 돌리면서 depth 구하고 그 과정에서 descendant 개수도 다 구함
2. 자식 노드들에게 하나하나 연락을 보내는데 descendant가 많은 놈부터 보냄. descendant 개수가 똑같은 경우 depth가 더 깊은 곳까지 가는 자식노드부터 보냄
3. 노드 각각의 도달 시간은 bfs로 계산하되 parent가 여러개인 경우가 있을수 있으니 중복 방문을 허용하고 최적해 갱신을 함
이게 아이디어인데 반례가 어떤게 잇을까요??
아직 제출은 안했고 생각나는 케이스 외에 랜덤케이스 만드는 코드 짜고있어요
푼사람 1명짜리 문젠데 여기 물어봐도 모르지 않을까..
1->(2, 3) / 3->4->5->6->7->8 / 2->(9, 10, 11) / 9->(12, 13, 14) / 10->(12, 13, 14) / 11->(12, 13, 14) 이게 반례일듯
섭트리 크기가 2는 6개고 3은 5개인데 2에서 섭트리 끝내는건 4초, 3에서 섭트리 끝내는건 5초라서 3부터 보내야 할것같음
아....감사합니다
나도 예전에 이거 좀 파봤는데 웬만한거 다 안됨.. 걍 논문대로 하셈
이거 논문 좀더 찾아봤는데 아까껀 트리에서만 적용 가능하기 때문에 저 문제에서는 안될것 같음.
https://arxiv.org/pdf/2107.06359.pdf
보면 트리는 선형 시간에 풀 수 있고 (
https://epubs.siam.org/doi/10.1137/0210052)
트리가 아닌 경우에는 NP-hard임.
exact solution을 구하려면 가능한 스패닝 트리 전부 완탐해서 그 스패닝 트리에 대해 각각 구해서 최소값 구하는 수밖에 없을것 같음 이게 TLE가 안난건 테케가 약해서 그런게 아닐지