안녕하세요, 반례 드릴게요

밑밑에 글 답변에서 분배가 잘못될 수 있다는 게 무슨 의미인지 아래 반례 보면서 확인해주세요

(저도 이 반례 찾으면서 네트워크 플로우 다시 공부할 수 있었습니다.)

앗. 좋은 반례 감사합니다. 사실 다른 방법으로 맞기만 했는데 이거 보면서 다시 한번 되뇌어 봐야 될 거 같아요.
그리고 이 반례가 네트워크 플로우를 공부하는 다른 분들께도 좋은 반례가 될 것 같습니다!
다시 한 번 감사합니다!

2년 전 댓글이긴 하지만, 보실 분 있을 수 있으니까 댓글 달게요 [[정답 주의]]

0->1에 k+n cap을 잡기 전, 먼저 일반적 bipartite matching문제로 인식하고 먼저 배분합니다. 이는 무슨 알고리즘을 써도 딱히 상관없을 것 같아요. 저는 0->1 cap을 n으로 잡고 max flow를 구했습니다.

이를 기록하고, 모든 사람이 일을 아예 안 해도 되고 최대 k의 일을 할 수 있도록 0->1에 k cap을 설정하고 이번에는 max flow로 접근합니다 (이때, 1->나머지 노드 들도 cap을 k로 놓아서 각 엣지별로 최대 k가 흐를 수 있도록 잡았습니다. 0->1이 k이기 때문에 어차피 k를 넘을 일은 없으니까요)

그래서 첫 번째 한 매칭과 두 번째의 max flow를 더하면 답이 나와요.

0->1에 k+n cap을 놓았정답 처리되지답처리되지 않고 0->1에 n cap 한 다음 0->1에 k cap을 한 후 max flow를 각각 구한 다음 합하면 정답이 나오는 이유는 0->1에 k+n cap을 잡으면 총 벌점이 k를 넘는 경우가 발생하기 때문입니다. 위 반례에서도 볼 수 있고요. k만큼플로우를 플로우를 보내고 모든 사람k씩대해 k씩 cap을 더하면 남이 벌점을 받지 않고도 기본적으로 하는 1의 일을 다른 사람이 가져가는 상황이 나타나기 때문입니다. 0->1에 n, 다음 k를 하면 이런 문제가 발생하지 않는 이유는 0->1에 n cap에 대해서는 벌점의 개념이 애초에 존재하지 않고 남의 일을 가져갈 그다음 그 다음 k cap에 대해서는 벌점만 바탕으로 계산하기 때문에 벌점문제이기 때문입니다때문입니다.