네트워크 플로우, minimum cost maximum flow 관련 질문 드립니다. ㅠㅠㅠㅠㅠ

  • chochogogo
    chochogogo

    안녕하세요?
    네트워크 플로우 관련 이론 중

    -기본 최대 유량 이론
    -이분 매칭
    -minimum cost maximum flow
    에 대해 공부하고 있는데요...

    -기본 최대 유량 이론
    -이분 매칭
    는 이해가 가는데....
    -minimum cost maximum flow는 어떻게 구현해야 할지 감이 안잡혀서요....
    (http://jungol.co.kr/problem.php?ctc=031200&id=1882 문제가 MCMF 문제 인것 같은데..ㅠㅠ)

    일단 해당 건 관련해서 알고 있는 것은....
    minimum cost maximum flow 구현 시 기존

    • capacity, flow 뿐 아니라 cost도 고려해 주어야 함.
    • 경로 구할 때, 기존 BFS, DFS 방식 이용하는 것이 아니라 cost 기준으로 밸만포드 알고리즘 이용 (cost가 음수일 수 있기 때문)

    여기서 궁금한 점이... 밸만포드로 확대경로 구한 후에 flow는 기존 알고리즘 대로 최저 flow 만큼씩 빼주면 되는 걸로 알고 있는데
    cost에 대한 처리는 어떻게 되어야 하는건가요...??

    그리고 솔직히 말씀 드리면, minimum cost maximum flow도 그냥 넘어 알고 있는 내용이라 제가 쓴 내용이 맞는지도 모르겠습니다...ㅠㅠ


    5년 전
15개의 댓글이 있습니다.
  • restart
    restart

    MCMF는 topcoder tutorial이 굉장히 정리가 잘 돼 있습니다. 벨만포드만을 이용한 구현에서는 cost 업데이트가 따로 필요 없고, 다익스트라를 이용하기 위해서는 1회 벨만포드 이후 node potential에 따른 cost reduction이 필요합니다~


    5년 전 link
  • restart
    restart

    https://www.topcoder.com/community/data-science/data-science-tutorials/minimum-cost-flow-part-two-algorithms/


    5년 전 link
  • chochogogo
    chochogogo

    답변 감사합니다~!
    여쭙고 싶은 것이 있는데요...
    답변 주신 링크에 flow 처리 시, flow 역 방향으로 cost를 음수 처리해주는 것도 처리해 줄 필요 없는 것인가요??
    (처리를 안해 주어도 flow 흐름에 따라 자동 음수 계산 되는 것인가요???)
    우문이라면 죄송합니다 ㅠㅠ


    5년 전 link
  • JongMan
    JongMan

    네트워크 플로우에서는 a에서 b로 X만큼의 flow가 흐르고 있다면, b에서 a로는 -X만큼의 flow가 흐르고 있다고 봅니다. 그래서 cost를 뒤집어 줄 필요는 없죠.


    5년 전 link
  • chochogogo
    chochogogo

    아하! 그렇군요!!!!!!!!!!!!!!!
    답변 감사합니다!!!
    아참 마지막으로 또 질문 드려도 될까요?ㅠㅠㅠ
    기본 network flow가 확대 경로가 없을 때까지 process를 진행한 후,
    t에 도달하는 flow의 합이 최대 유량이 되는데,
    MCMF의 경우, 동일하게 확대 경로가 없을 때까지 process를 진행(단, cost 기준으로), 확대 경로를 찾을 때마다다(t에 도착할 때마다) flow를 갱신해 주기 위해 t로부터 역탐색을 하게 되는데, 이때 임의의 변수x에 해당 경로의 cost들의 총 합을 계속 더해줌.
    확대 경로가 없을 때까지 process 진행 후 x의 값이 minimum cost이다.
    가 맞는 것인가요??
    자꾸 질문드려 죄송합니다 ㅠㅠ


    5년 전 link
  • restart
    restart

    각 엣지에 대해서 정방향의 cost를 C로, 역방향의 cost를 -C로 설정하면 shortest path를 찾을 때마다 flow*cost의 총합을 구하면 minimum cost가 됩니다. topcoder tutorial 중간에 나온 그림을 보면서 손으로 따라그려 보시면 큰 도움이 될거에요..


    5년 전 link
  • JongMan
    JongMan

    실제 구현을 보시면 참고가 될 것 같아 링크합니다.


    5년 전 link
  • chochogogo
    chochogogo

    두분 다 친절한 답변 정말 감사합니다~!!!!!!!!!!!!!!


    5년 전 link
  • chochogogo
    chochogogo

    JongMan님께서 올려주신 링크 보았는데요~~
    질문이 드리고 싶은게 생겨서요..ㅠㅠ,
    Ver1. 에서
    if(flow[v][u] > 0)
    cand = distance[u] - cost[v][u];
    else if(cap[u][v] > flow[u][v])
    cand = distance[u] + cost[u][v];

    if(cap[u][v] > flow[u][v])
    if(flow[u][v] < 0)
    cand = distance[u] - cost[v][u];
    else
    cand = distance[u] + cost[u][v];
    로 생각해도 될까요???ㅠㅠ


    5년 전 link
  • JongMan
    JongMan

    같다고 생각하셔도 될 것 같네요.


    5년 전 link
  • chochogogo
    chochogogo

    매번 질문 드릴때 마다 답변 주셔서 감사합니다~!
    주말 잘 보내세요~~


    5년 전 link
  • chochogogo
    chochogogo

    종만님께서 코드 공유해 주신것 공부한 덕분에 문제를 풀 수 있었습니다!
    (위의 문제 아닌 다른 문제)
    근런데 ver1로 문제를 풀었는데 답은 모두 정상적으로 나오는데 시간 초과가 되더라구요. 그래서 ver2(우선순위 큐 이용)을 공부하여 코드 구현중에 질문하고 싶은것이 있어 글 남기게 되었습니다.

    여쭙고 싶은 내용 :
    1. 제가 C로 구현하고 있는데, 우선순위 큐를 구현하기 위해 배열을 잡아 힙을 구현하였는데, 크기를 얼마나 잡아야 하는지 여쭙니다... 원래 다익스트라의 경우, 출발지가 됬던 정점은 checked(visited) 처리가 되어 pq에 인큐 안하는데 해당 case에서는 pq 배열의 크기를 얼마나 잡아야 하는 건지 여쭙니다 ㅠㅠ
    2.
    int cost = -pq.top().first;
    pq.push(make_pair(-thereCost, there)); 에서 -pq.top().first와thereCost앞에 -붙는 이유

    위의 두가지 여쭙니다.
    감사합니다.
    수고하십시오~!


    5년 전 link
  • chochogogo
    chochogogo

    2번 질문 같은 경우는
    알고리즘 문제 해결전략에서, priority_queue는 기본적으로 가장 큰 원소가 위로 가도록 큐를 구성하기 때문에 거리의 부호를 바꿔서 거리가 작은 정점부터 꺼내지도록 하는 것에 주목합시다.
    라고 적어주신 것처럼, STL이 가장 큰 원소가 위로 가도록 구현 되어 있기 대문에 그런것 인가요??


    5년 전 link
  • JongMan
    JongMan

    1번 질문의 경우.. 음수 사이클이 없다면 간선의 개수만큼 잡으면 될 것 같은데요.
    2번 질문은 말씀하신 것이 맞습니다.


    5년 전 link
  • chochogogo
    chochogogo

    답변 감사합니다!


    5년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.