naong606   4년 전

10786번 Catering 문제를 해결하면서 애매한 부분이 있어 질문드립니다.
문제에서 요구하는 것이 최소비용이여서 처음에는 i -> j로 가는 cost가 주어지더라도 
다른 경로를 통해 더 작은 cost로 갈 수 있다면 i -> j로 바로가는 cost 대신에 
그 경로의 cost로 update한 후에 mcmf를 구현했는데 WA가 나왔습니다.

예를 들면, C12 = 1, C13 = 100, C23 = 1라고 입력이 들어온 경우, C13 = C12 + C23과 같이 더 작은 비용으로 update했습니다.


실제로는 위와 같은 전처리 과정을 생략하니 ACC가 나왔네요.
현재 문제에 주어진 cost는 moving cost인데, 양 끝점에서 꼭 catering을 해야 된다는 조건이 없어서
현재 조건만으로는 위와 같이 전처리를 한 후에 mcmf를 돌려야 하는게 아닌가 하는 생각이 들었습니다.

감사합니다!

qkdtmdeh   3년 전

양 끝점에서 catering을 해야한다는것이 company의 위치 즉 1번 정점에서 시작해야한다는 뜻인가요???

저도 이 문제를 보면서 궁금한 점이 하나 생겼는데,,,

catering team의 갯수때문에 source에서 1번정점으로 연결하는 간선의 용량을 team의 갯수로 했을때, 그러면 최대 유량이 아무리 커져도 team갯수만큼까지밖에 안될 것 같아서 이 문제를 어떻게 해결해야하는지 궁금합니다. 만약 용량을 request갯수로 두면 team의 갯수보다 더 많은 team이 company에서 직접 각 정점으로 가는 경우가 생길 것 같아서요.. 이걸 어떻게해결해야하죠??

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