wn1op   2년 전

저는 이 문제를 다익스트라를 응용하여서, 기본적으로 shortest path를 찾을 때는 minHeap을 이용해서 거리가 짧은 순으로 찾아가는 것을, 이 문제에서는 

1. max Heap을 이용해서 현재 그 노드에 가장 많은 flow를 흘릴 수 있는 노드를 찾는다.

2. shortest path 찾기에서의 현재 찾은 최단 거리와 S'에 들어가는 원소에서의 cost + S'에 들어가는 원소 cost를 비교하여 작은 것으로 갱신 => 이 문제의 경우 min( S'에 들어가는 원소로의 flow, S'에 들어가는 원소에서의 cost)를 현재 찾은 최대 flow와 비교하여 큰 것으로 갱신

이런식으로 해서 s->e로의 max flow route를 찾았습니다. 예제는 잘 계산되고, s에서 다른 모든 점으로의 max flow도 잘 계산되는 것을 확인했습니다. 현재 알고리즘에서 어느부분이 문제가 있을까요? 8%에서 틀렸습니다가 나옵니다.

wn1op   2년 전

같은 vertex간에 다른 무게제한을 가진 다리가 여러개 있을 경우를 고려하여 각 edge vector를 cost를 기준으로 내림차순으로 정렬하여, 같은 vertex 간에서 가장 큰 무게제한을 가진 다리가 반드시 먼저 고려되도록 수정하였습니다. 하지만, 동일한 8%에서 틀렸습니다가 나오네요 ㅠㅠ

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