MATCHFIX 책의 내용에 대한 질문 입니다.

  • 7041701
    7041701

    안녕하세요.

    제가 생각하는 논리가 맞는지 궁금합니다.

    canWinwith 밖에서 0번선수가 남은 경기 모두 이길시 totalWins 이상을 할 수 있는지에 대한 검사를 하고, 가능하다면 canWinwith를 조사하는 방식인데,

    0번선수가 (자신이 속한)남은 경기 모두 이길시 totalWins 이상을 할 수 있고,

    나머지 선수들이 totalWins 한 사람들이 없고,

    newflow 를 m배분 가능하다면
    (m 배분이 가능해야하는 이유는 0번이 속하지 않은 경기들도 간선용량이 totalWins에 제한 받아 종속적이기 때문에 '승수내보내기'가 안될 경우도 있으므로, 경기가 이루어지지 않고 남는 경기가 생기면 안되므로)

    가능한 조건속에서 newwork(0,1) == m 체크를 마지막으로 해야하는 것.

    위의 논리가 맞나요??

    또한, 덧붙여 시간복잡도를 totalWin를 0->M으로 1씩 늘려가지 않고
    마지막으로 찾은 최대 유량에서부터 다시 포드-풀커슨을 시작한다고 하였는데, 이 부분에 대해서 약간의 코드적인 부분가 덧붙여 설명해주신다면 감사하겠습니다. 추상적으로 이해되고 명시적으로 이해가 되지 않아서..

    감사합니다.


    5년 전
1개의 댓글이 있습니다.
  • JongMan
    JongMan
    1. 맞는 것 같습니다.
    2. 구체적으로, flow 배열을 0으로 초기화하지 않는다는 의미입니다.

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