4개의 댓글이 있습니다.
-
-
Chaos.PP -
아, AOJ 에 있어서 따로 링크를 안걸었는데 죄송합니다^^;
http://algospot.com/problems/read/JOGGER
위의 링크이고요, 문제는 양방향 가중치 그래프에서 리프의 개수와
어떤 두 리프간의 거리만 주어졌을 때(즉 내부 노드의 구조와 가중치는
알 수 없습니다. 그리고 두 리프간의 도달하는 경로는 유일합니다.) 주어진
식을 만족하는 가장 긴 리프 노드간의 패스를 찾는 것입니다. 주어진 식은
다음과 같습니다.
식 = (해당 패스의 가중치의 합) * r + (내부 노드의 개수) * t
여기서 r과 t는 입력으로 주어집니다.
13년 전 link
-
-
-
JongMan -
음.. 안풀어봤지만, 어려운 부분은 최단거리 매트릭스에서 스패닝 트리를 만드는 부분인 것 같은데, 최단거리 매트릭스에서 최소값을 찾아내면 그 두 정점은 직접 간선으로 연결되어 있음이 확실해진다는 점을 깨달으시면 푸실 수 있을거 같습니다.
다시 말해 (i, j, distance[i][j]) 를 거리 순으로 오름차순 정렬하고, 하나하나 그래프에 추가해 나갑니다. 이전에 추가한 간선들로 distance[i][j] 를 얻을 수 있을 경우 해당 간선은 버리시면 되지요. 플로이드 알고리즘을 응용하시면 O(N^4) 에 해당 트리를 만드실 수 있을 거 같습니다..
13년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
Chaos.PP
이 문제를 읽어 봤는데 도통 방법이 생각이 나질 않네요.
혹시 힌트나 해법을 좀 알려주시면 감사하겠습니다.
13년 전