smu201111192   4년 전

MCMF로 그대르 모델링을 해서 ac를 받았습니다.

그래프 모델링한걸 간단히 설명해드리자면

1.상대팀을 이길 수 있다면 cap=1,cost=-2  (2점을 얻을 수 있음)

2.비기는 경우라면 cap=1,cost=-1 (1점을 얻을 수 있음)

3.지는 경우라면 cap=1,cost=0 (0점을 얻을 수 있음)

이렇게 모델링하고 ac를 받았습니다.

그런데 3번의 경우는 굳이 고려를 안 해줘도 되지않을까요?(얻을 수 있는 점수가 전체 점수에 영향을 안 줄거 같습니다.)

도움 부탁드립니다!.







koosaga   4년 전

4

5 4 3 2

4 3 2 1

왜 문제가 되는지는 혼자 생각해보세요. 


코스트가 0이라는 이유로 모델링한 그래프를 마음대로 바꾸지 마세요!

smu201111192   4년 전

아... maxflow가 안 만들어 질 수가 있군요!

감사합니다. 구사과님!

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