17412번 - 도시 왕복하기 1
AC는 받았습니다만
순방향 간선의 capacity는 유지해주고 역방향 간선의 capacity를 삭제하니까 맞더라구요...
네트우크 플로우 입문중인데 개념이 잘 잡히지 않습니다.
이 문제에서 역방향 간선의 capacity를 삭제해주어야 하는 이유는 무엇인가요?
하나의 경로가 정해지면 그 경로를 변경해줄 필요가 없기때문인가요?
역방향의 음수 플로우로 경로를 변경해준다 해도 최대유량이 나오는건 똑같지 않나요? 잘 모르겠습니다. 조언 주시면 감사하겠습니다.
간선이 단방향이라서 그런거아닐까요?
도시왕복하기2는 양방향이고
도시왕복하기1은 단방향입니다
댓글을 작성하려면 로그인해야 합니다.
opop20207 4년 전 1
AC는 받았습니다만
순방향 간선의 capacity는 유지해주고 역방향 간선의 capacity를 삭제하니까 맞더라구요...
네트우크 플로우 입문중인데 개념이 잘 잡히지 않습니다.
이 문제에서 역방향 간선의 capacity를 삭제해주어야 하는 이유는 무엇인가요?
하나의 경로가 정해지면 그 경로를 변경해줄 필요가 없기때문인가요?
역방향의 음수 플로우로 경로를 변경해준다 해도 최대유량이 나오는건 똑같지 않나요? 잘 모르겠습니다. 조언 주시면 감사하겠습니다.