canWinwith 밖에서 0번선수가 남은 경기 모두 이길시 totalWins 이상을 할 수 있는지에 대한 검사를 하고, 가능하다면 canWinwith를 조사하는 방식인데,
0번선수가 (자신이 속한)남은 경기 모두 이길시 totalWins 이상을 할 수 있고,
나머지 선수들이 totalWins 한 사람들이 없고,
newflow 를 m배분 가능하다면
(m 배분이 가능해야하는 이유는 0번이 속하지 않은 경기들도 간선용량이 totalWins에 제한 받아 종속적이기 때문에 '승수내보내기'가 안될 경우도 있으므로, 경기가 이루어지지 않고 남는 경기가 생기면 안되므로)
가능한 조건속에서 newwork(0,1) == m 체크를 마지막으로 해야하는 것.
위의 논리가 맞나요??
또한, 덧붙여 시간복잡도를 totalWin를 0->M으로 1씩 늘려가지 않고
마지막으로 찾은 최대 유량에서부터 다시 포드-풀커슨을 시작한다고 하였는데, 이 부분에 대해서 약간의 코드적인 부분가 덧붙여 설명해주신다면 감사하겠습니다. 추상적으로 이해되고 명시적으로 이해가 되지 않아서..
7041701
안녕하세요.
제가 생각하는 논리가 맞는지 궁금합니다.
canWinwith 밖에서 0번선수가 남은 경기 모두 이길시 totalWins 이상을 할 수 있는지에 대한 검사를 하고, 가능하다면 canWinwith를 조사하는 방식인데,
0번선수가 (자신이 속한)남은 경기 모두 이길시 totalWins 이상을 할 수 있고,
나머지 선수들이 totalWins 한 사람들이 없고,
newflow 를 m배분 가능하다면
(m 배분이 가능해야하는 이유는 0번이 속하지 않은 경기들도 간선용량이 totalWins에 제한 받아 종속적이기 때문에 '승수내보내기'가 안될 경우도 있으므로, 경기가 이루어지지 않고 남는 경기가 생기면 안되므로)
가능한 조건속에서 newwork(0,1) == m 체크를 마지막으로 해야하는 것.
위의 논리가 맞나요??
또한, 덧붙여 시간복잡도를 totalWin를 0->M으로 1씩 늘려가지 않고
마지막으로 찾은 최대 유량에서부터 다시 포드-풀커슨을 시작한다고 하였는데, 이 부분에 대해서 약간의 코드적인 부분가 덧붙여 설명해주신다면 감사하겠습니다. 추상적으로 이해되고 명시적으로 이해가 되지 않아서..
감사합니다.
8년 전