SWERC 2013 regional 문제중 b번 질문드려요.

  • yeonzzg
    yeonzzg

    문제가 넘 어려워서 공홈 solution을 봤는데 뭔가 이상해서
    질문드려요.

    문제링크

    intended solution 보면 각 course마다 그냥 (# of student / capacity of room)으로 flow를 잡고 maximum flow로 풀던데..
    근데 제가 느끼기에 이 문제가 어려웠던게 room의 용량을 다 안쓰고
    학생을 적절히 나눠서 arrange하면 최적해가 나오는 예가 있었거든요..

    아래와 같이,
    1
    3 4
    1 5 8
    11 15 2
    20 25 8
    0 1 100
    0 0 1
    0 0 0

    와 같은 예가 있으면 2번 course는 학생이 2명이고 room의 용량은 4지만,
    1명씩 나눠서 2방으로 불려서 계교다리로 쓰면 최적해가 2가 나오는
    예제인데.. 공홈 solution으로 돌려보니까 3이 나오네요 ㅠ
    뭔가 제가 문제를 잘못 이해한거같긴 한데 아무리 다시 읽어도 다른
    제한을 못찾겠네요 ㅠ


    5년 전
0개의 댓글이 있습니다.
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.