6개의 댓글이 있습니다.
-
-
amok -
"0번선수 to sink의 flow가 capacity만큼 꽉 차 있어야 한다는 조건을 반드시 확인해야 하는 것 아닌가요?"
저도 그 부분을 고민해 보았는데, 그 조건을 확인하지 않아도 된다는 결론을 얻었습니다. 실제로 그 조건을 확인하지 않는 코드를 작성해서 정답 판정을 받기도 했습니다.
네트워크의 최대 유량이 m이라면, 0번 선수에서 sink로의 간선의 용량을 꽉 채우면서 총 m만큼의 유량을 흘려보내는 방법이 반드시 존재합니다. 포드-풀커슨 알고리즘의 핵심은 dfs냐 bfs냐가 아니라, source에서 sink로 가는 유량을 더 흘려보낼 수 있는 경로를 더 이상 찾을 수 없을 때까지 찾는다는 것에 있습니다. 그러한 경로를 찾는 순서는 중요하지 않습니다. 어떤 순서로 경로를 찾아서 유량을 흘려보내든, 우리는 네트워크의 최대 유량에 도달합니다. 그렇다면 0번 선수를 sink로 연결하는 간선을 거치는 경로들부터 먼저 찾아내서, 그 간선의 용량을 꽉 채우도록 유량을 최대한 흘려보내면 되겠지요. (0번 선수가 참가하는 경기들이 있다면 0번 선수가 totalWins만큼 이길 수 있도록 그 경기들의 승패를 다른 경기들의 승패보다 먼저 조작해 놓는다는 것입니다.) 그 이후로 어떻게 경로를 찾아서 유량을 흘려보내든 우리는 이 네트워크의 최대 유량에 도달합니다. 즉, 이미 이 네트워크의 최대 유량이 m임을 확인했다면, 0번선수 to sink간선의 용량을 꽉 채우도록 유량을 흘려보내는 방법도 반드시 존재한다는 것입니다.
물론 0번이 참가하는 모든 경기를 0번이 이겨도 totalWins에 도달할 수 없을 정도로 totalWins가 매우 크다면, 0번 선수에서 sink로 가는 간선의 용량도 매우 커지기 때문에, 그 간선의 용량을 꽉 채울 수 없습니다. 하지만 이 경우는 어떻게 승부를 조작해도 0번이 우승할 수 없는 것을 의미하기 때문에, canWinWith()를 호출할 필요조차 없겠지요.
8년 전 link
-
-
-
7041701 -
안녕하세요.
제가 생각하는 논리가 맞는지 궁금합니다.
canWinwith 밖에서 0번선수가 남은 경기 모두 이길시 totalWins 이상을 할 수 있는지에 대한 검사를 하고, 가능하다면 canWinwith를 조사하는 방식인데,
0번선수가 (자신이 속한)남은 경기 모두 이길시 totalWins 이상을 할 수 있고,
나머지 선수들이 totalWins 한 사람들이 없고,
newflow 를 m배분 가능하다면
(m 배분이 가능해야하는 이유는 0번이 속하지 않은 경기들도 간선용량이 totalWins에 제한 받아 종속적이기 때문에 '승수내보내기'가 안될 경우도 있으므로, 경기가 이루어지지 않고 남는 경기가 생기면 안되므로)가능한 조건속에서 newwork(0,1) == m 체크를 마지막으로 해야하는 것.
위의 논리가 맞나요??
또한, 덧붙여 시간복잡도를 totalWin를 0->M으로 1씩 늘려가지 않고
마지막으로 찾은 최대 유량에서부터 다시 포드-풀커슨을 시작한다고 하였는데, 이 부분에 대해서 약간의 코드적인 부분가 덧붙여 설명해주신다면 감사하겠습니다. 추상적으로 이해되고 명시적으로 이해가 되지 않아서..감사합니다.
7년 전 link
-
-
-
canuyes -
혹시나 도움이 될까하는 마음에,
또, 나중에 분명 까먹을 저를 위해 답글 달아둡니다.<0번 선수, sink>의 flow와 capacity가 같아야한다.는 맞는 이야기라고 생각합니다.
i번 선수(i != 0)에게 totalWins - 1 - wins[i]를 추가로 챙길 수 있는 승수로 할당해놓고 정작 0번 선수 자신은 totalWins - wins[0] 미만으로 할당 받는다면 리그에서 우승할 수 없으니까요.하지만, 이걸 굳이 체크해주거나 별도로 구현해줄 필요는 없다고 생각합니다.
source에서 sink로의 max flow가 m(경기수)이라면 <0번 선수, sink>의 flow와 capacity를 같게 만들 수 있다를 증명하면 이를 알 수 있겠지요.source에서 sink로의 max flow가 m이라는 이야기는 곧 sink로 들어오는 간선의 flow의 총 합이 m이라는 이야기 입니다.
이 때, <0번 선수, sink>.flow < <0번 선수, sink>.capacity라고 해봅시다.
자명하게 <0번 선수, sink>.capacity <= m이 만족하므로 m - <0번 선수, sink>.flow만큼의 flow는.flow(x != 0)를 통해 sink로 흘러 들어오고 있을 것 입니다.
이러한 x번 선수들 중 predecessor(경기 노드)가 successor로 0번 선수를 갖는 선수들만을 생각해봅시다.
이런 선수들은 predecessor로부터 자신으로 오는 flow를 1 감소시키는 대신 predecessor로부터 0번 선수로 가는 flow를 1 증가시켜주므로서 <0번 선수, sink>.flow를 1 증가시킬 수 있습니다.
이제 이런 선수들을 찾아서 <0번 선수, sink>.flow가 <0번 선수, sink>.capacity와 같아질 때까지 반복해주면 됩니다.
주어진 m개의 경기 중에서 0번 선수가 참여하는 경기의 수를 k개라고 할 때 애초에 totalWins - wins[0] <= k가 만족해서 포드-풀커슨 알고리즘을 통해 확인하는 중이므로,
(만족하지 않았다면 답은 -1일 것 입니다.)
이러한 반복은 <0번 선수, sink>.capacity를 가득 채울때까지는 반복할 수 있습니다.아, 그리고 참고로 전 아직 안풀엇네요 ㅎ
주말에 해야지 ㅎ
7년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
amievil2
안녕하세요.
책을 구입해서 공부하고 있는 사람입니다.
책의 뒷부분에 MATCHFIX 문제에 대해 이상한 것이 있어 질문 드립니다.
책의 예제 코드 내용대로라면(page 1009) totalwins를 1씩 증가 시키고 이 것에 따라 각 선수 to Sink로의 Capacity를 적절히 분배하여 네트워크 flow가 최초로 M가 같아 지는 부분에서 정답을 찾는 것으로 되어 있습니다.
그런데 제 생각에는 확인해야할 조건이 하나 빠져 있는 것 같습니다. 0번선수 to sink의 flow가 capacity만큼 꽉 차 있어야 한다는 조건을 반드시 확인해야 하는 것 아닌가요?
단지 network의 capacity를 분배후에 m 만큼의 flow가 있다는 조건만으로 정답여부를 말할 수 있을 것 같지는 않습니다.
이 부분에 대해 제가 잘못 알고 있는 것인가요?
혹시 잘 아시는 분 설명 부탁드리겠습니다.
10년 전