kkw564   2년 전

이 문제에서 능력치를 입력받게 되는데요

능력치가 0이어도 cost가 0인 엣지를 생성시켜주면 mcmf에서 반례가 될 상황이 어떤경우가 있는건가요?

아래 3가지 경우를 들어두었습니다.

행여나 전체 코드가 필요하다면 말씀해주시면 다시올리겠습니다.

ntopia   2년 전

min cost max flow 를 찾는다면

cost 가 0인 간선에도 유량이 흐르도록 하는 flow 를 찾을텐데요 (max flow 를 찾으니까)

문제 조건에 능력치가 0이면 배정을 아예 하면 안된다고 했으니, 결국 이러면 오답이 나오는거죠.

kkw564   2년 전

하지만 어떠한 경우에도 cost가 음수인 값은 주어지지 않으니 능력치가 0~100사이면

0이 항상 최댓값을 가지기때문에 0을 포함한 포지션 결과값은 절대 나올 수 없지 않나요?

제 생각의 어느 부분에 착오가 있는지 알려주시면 감사하겠습니다.

ntopia   2년 전

무슨 말인지 잘 모르겠네용...


mcmf 가 구하는게  가능한 max flow 들 중에서 cost가 최소인 것 이잖아요?

그러니까 cost가 0인 간선으로도 유량이 흐르게 될텐데, 이게 문제가 되는거 아닌가요?

kkw564   2년 전

아 무슨말인지이해했습니다 감사합니다!!

ntopia   2년 전

보충 설명을 드리자면

어떤 선수가 cost가 0인 포지션으로 배정되어버리는 바람에
다른 선수가 원래 배정되어야할 곳에 배정되지 못하고 다른 곳으로 배정되는데
하필이면 그게 전체 cost의 합을 더 작게 만들어버리는 경우가 존재하는 것 같네요

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