밑글 최단경로 글쓴이입니다.
해당 상황에서 MCMF를 어떻게 해야 할까요??
저는 네트워크 플로우도 할 줄 모르는 바보이지만 도전해보겠습니다.
혹시 제가 말한 상황과 비슷한 문제 알고 계신다면 알려주셨으면 합니다.
뉴비에게 큰 도움이 될 것입니다.
감사합니다.
해당 상황에서 MCMF를 어떻게 해야 할까요??
저는 네트워크 플로우도 할 줄 모르는 바보이지만 도전해보겠습니다.
혹시 제가 말한 상황과 비슷한 문제 알고 계신다면 알려주셨으면 합니다.
뉴비에게 큰 도움이 될 것입니다.
감사합니다.
한 번만 지날 수 있는 간선은 최대유량을 1로 나머지 간선은 무한대로 놓고 유량을 1만 흘렸을 때 비용을 구하면 되려나요? ㅜㅜ 뉴비 대가리 깨지는중
그렇게 놓고 유량을 계속 흘리면서 경로가 양수가 될때까지 해줘야 함
만약 시작 그래프에 음수 간선 사이클이 있다면 사이클을 지워주는 사전 처리도 필요함
짤 수는 있을텐데 정확히 짜려면 고려할게 좀 있네
사이클 다시 생각해보니까 있으면 처리하기가 너무 어려움
답변 감사드립니다 ^^ 역시 갓갓 갤주님 밑의 유동 분도 고마워요