kalmiaa   5달 전

저는 샘플인풋도 손으로 못풀겠습니다.

edge list를 만드는 중에 cycle은 허용하는지. node의 재방문은 허용하는지,
node라고하면 시작 끝 node도 포함인지 여부가 전혀 적혀있지 않습니다.


noeffserv   5달 전

어떻게 이해하셨는지는 모르겠지만, 정점 u,v 사이의 경로가 존재하는 한 '그래프' 내에 있는 최소 간선을 제거해나가는 것입니다.

kalmiaa   5달 전

샘플의 답을 보면 u->v 사이에 어떤 경로가 존재할때, node를 2번 거칠 수 있는것 같습니다.

edge는 한번씩인것 같구요.

그런식으로 접근했는데도 샘플답인 256에 미치지 못하네요.

그렇다면 edge를 한번씩만 접근한다는 전제하에

u->x->v->y->v 와 같은것도 가능한건가 해서요.


다들 잘 푸시는거 같은데 제가 이해가 딸리나 봅니다.

손으로 풀어도 256이 안나오네요 ㅋㅋ

ntopia   5달 전

node를 2번 거친다, edge를 한번 거친다  이런 말은 문제와 전혀 관련 없습니다. 무슨 말씀을 하고 계신건지 잘 모르겠어요.


먼저 u, v가 결정됐을 때 Cost(u, v) 의 값을 구하는 과정을 이해하고 계신가요?


Cost(u,v)는 다음에서 제거되는 간선들의 가중치 합이다: u와 v사이의 경로가 있으면 이 그래프의 최소 가중치 간선을 그래프에서 제거한다. 이 과정을 u와 v사이의 경로가 없을 때까지 반복한다.

문제 본문에서 Cost(2, 6) 을 계산하는 과정을 잘 읽어주세요.

Cost(2,6)을 구하는 과정에서 제거되는 간선들을 차례대로 나열하면 다음과 같다: (2, 3), (4, 5), (3, 5), (3, 4), (2, 6).

왜 저렇게 5개의 간선이 제거되느냐? 하면

맨 처음 상태에서 2와 6 사이에 경로가 존재하니, 그 그래프에서 가중치가 제일 작은 간선인 2-3 이 선택되어 제거됩니다.

그 다음에 남은 그래프에서 또 2와 6 사이에 경로가 존재하니, 그 그래프에서 가중치가 제일 작은 간선인 4-5 이 선택되어 제거됩니다.

이런 식으로 남은 그래프에서 2와 6 사이에 경로가 존재하지 않을 때 까지 반복하고, 삭제된 간선의 가중치들을 다 더한 값이 Cost(2, 6) 이 됩니다.


u, v가 결정됐을 때 Cost(u, v)를 계산할 수 있습니다.

그럼 이제 우리가 해야하는 일은

간선에 가중치가 있는 그래프가 주어질 때, u<v인 모든 두 정점 u,v에 대한 Cost(u,v)들의 총 합을 구하는 프로그램을 작성하시오.

입니다.

그럼 이제 모든 정점 쌍 (1, 2), (1, 3), (1, 4), (1, 5), ..., (2, 3), (2, 4), (2, 5), ..., ..., (4, 5)

에 대해 Cost(u, v) 값을 구해서 다 합한 값을 출력하면 되는 겁니다.


kalmiaa   5달 전

문제의 예시인 Cost(2,6)에서 보면 지울수있는 edge의 후보군은

2,3,4,5,6,15 죠.

그중에 edge cost 3,4,5는 Vertex 3번을 반드시 거치고 나야만 갈수있는 곳입니다.

Vertex 기준으로 2->3->4->5->3->6 이런식으로요.

Cost(2,6)에서 유추할 수 있는 최소조건은 중간경로의 Vertex는 여러번 방문해도 되지만 Edge는 한번씩만 방문할 수 있다는 거겠죠.

이런건 당연히 안될거잖아요. Vertex 기준으로 2->1->2->6(Edge를 2번 방문하니까요)


그리고 다른 예로 Cost(2,3)을 들면 

Vertex 기준으로 2->6->3 으로 가는 경로가 있겠고, 2->3 으로 바로 가는 최단거리 경로도 있겠죠.

거기서 쓸 수 있는 edge는  2,6,15 겠구요.

그러면 2->3->4->5->3 도 Cost(2,3) 즉 2->3 으로 가는 경로라고 볼 수 있냐는 질문입니다.

제 상식선에서는 중간에 destination Vertex를 방문해버렸고, 3번 Vertex를 방문하지 않고서는 4, 5번 Vertex는 방문할 수 없는데,

이미 Destination을 방문하고나서 가능한 edge도 부분경로에 포함시킬 수 있냐는 질문입니다.


이것은 Cost(2,6) 과는 다른 방식이죠.

ntopia   5달 전

아니요 그런 이야기가 아닙니다.

그냥 u와 v 사이에 임의의 경로 아무거나 존재하면 되는 것 입니다.

경로가 아무거나 하나 존재하면

그 경로 상에 있는 간선과는 상관없이

남은 그래프 안에서 가중치가 가장 작은 간선을 제거하는 것 입니다.

ntopia   5달 전

u 에서 v로 가는 경로는 당연히 여러가지가 존재할 수 있고

삭제할 간선은 그 경로 상에 있는 간선과는 무관하게 고르는 것 입니다.

kalmiaa   5달 전

이제 이해했습니다.

지우는건 그냥 전체그래프내에서 작은놈부터 지우는거군요.

설명 듣고 문제 다시 읽으니 그렇게 쓰여져 있네요.. 

부끄럽습니다 -_-;;


감사합니다.

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