ckdgus2482   1년 전

src노드에서 branch노드까지 capacity를 N+K로 줬고 branch에서 각각의 직원 노드 까지 capacity를 2로 줬습니다.

그리고 직원 노드에서 일 노드의 capacity는 입력에서 주어진 매칭에 대해서 capacity를 1씩 줬으며 각각의 일 노드에서 sink노드 까지 capacity를 1 줬습니다.

예제입력에 대해서는 잘 작동하는데 제출하니까 40%가량 올라가다가 틀렸다고 나오네요.

제 네트워크 모델링에 무슨 오류가 있는지 봐주시면 감사하겠습니다.

exqt   1년 전

저도 그렇게 생각했는데 반례가 있는거 같아요

정확한 반례는 못찾겠고.. ㅠㅠ

4d26cb121d713366e1fd255b5fed518e.png

이렇게 하는게 맞는거 같아요

ckdgus2482   1년 전

확실히 그 방법이 더 명확하긴 하네요. 답변 감사합니다.

kdhsong   1년 전

branch노드가 무엇인가요?


src -> 직원 -> 일 -> 싱크 아닌가요?ㅠ

ckdgus2482   1년 전

그냥 제가 그렇게 모델링한거에요.

src->branch->직원들->일들->싱크 이렇게 한겁니다.

kdhsong   1년 전

아! 그렇군요 감사합니다!

3 4 1


2 1 2


1 2


2 3 4


한번 해보시길 바랍니다.


또는 예를 들어서 10명의 사람 중 2명만 일을 2개씩 할 수 있는데 N+K=12를 주게 되버리면 내부적으로 최대 6명까지 일을 2개씩 할 수 있을 것 같습니다.

ckdgus2482   9달 전

blinkingstar님이 주신 입력 예에서는 답이 4로 알맞게 나옵니다.

그리고 N이 10, K가 2인 경우 최대 6명까지 일을 2개씩 할 수 있을 것같다고 하셨는데 그게 왜 문제가 되는건지 모르겠습니다.

최대로 일할 수 있는 개수를 구하는 문제이지 일의 분배를 최대한 균등하게 하라는 조건은 없지 않습니까?

4명이 쉬고 6명이 각각 일을 두개씩 맡아서 12개의 일을 끝낼 수 있다면 그걸로 된 것 아닙니까?

문제조건을 잘 읽어보시면 K명까지만 일을 2개 할 수 있습니다!


만약 K를 넘어버리는 인원이 2개의 일을 하게 되면 문제조건에 위배되는 거겠지요

ckdgus2482   9달 전

제가 잠시 미쳤었나봅니다. 멍청한 소릴 해놨네요.

반례 이해했습니다. 감사합니다.

댓글을 작성하려면 로그인해야 합니다.