2010 프로야구 질문드립니다.

  • bluefa
    bluefa

    2010 프로야구 문제를 유량 네트워크로 풀려고 하는데요.

    (유량네트워크 구조)
    소스 -- 경기 -- 팀 -- 싱크

    8개의 팀중 4개의 팀을 선택(자신이 응원하는 팀은 제외)해서

    팀에서 싱크로 가는 용량을 제한하는 식으로 풀려고 합니다.

    소스 에서 경기로 가는 용량의 크기는 1 이고 , 경기 -- 팀으로 가는

    2개의 간선을 갖게 됩니다. (예를 들어 hh팀 ns팀으로 입력이 주어졌을 때,

    경기에서 팀으로 가는 간선은 hh 팀 , ns 팀 각각 1개씩 있습니다.)

    그리고 팀에서 싱크로 가는 용량은 남은 경기에서 이길 수 있는 숫자 입니다.

    여기서 미리 자신이 응원하는 팀은 소스에서 -- 경기로 가는 간선을 0으로 막아놓음으로써 미리 계산에서 제외시켰습니다. 자신이 응원하는 팀이 승률이 높으면 높을 수록 좋다고 생각했기 때문에.

    그리고 4개의 팀을 선택하고 팀에서 싱크로 가는 간선은 최대 이겨도 되는

    횟수로 지정하게 했습니다. 나머지 선택에서 제외된 팀의 팀-- 싱크 용량은

    무한대입니다.

    그렇다면 유량네트워크함수가 반환하는 값이 남은 경기수 - (위에서 미리 제외시킨 값 ) 이 되면 참이 되도록 만들었는데요.

    그런데 계속 WA 를 받게 되는데, 제가 생각한 문제풀이 방법이 어디서

    잘못되었는지를 몰라서 질문드립니다. 감사합니다.


    9년 전
7개의 댓글이 있습니다.
  • hyunhwan
    hyunhwan

    여기서 미리 자신이 응원하는 팀은 소스에서 -- 경기로 가는 간선을 0으로 막아놓음으로써 미리 계산에서 제외시켰습니다. 자신이 응원하는 팀이 승률이 높으면 높을 수록 좋다고 생각했기 때문에.

    이 부분에서 혼동이 오는데, 혹시 소스가 하나의 노드가 아니라 팀으로 이뤄진 여러개의 노드로 이뤄진 것을 이야기 하나요?

    그리고 한번 데이터를 넣어 테스트 해본 결과, 다음의 종류의 데이터에서 잘못된 결과가 나오는 것을 확인했습니다. 참고 하시길 바랍니다.


    모든 8팀이 0승 0무 0패고, 잔여경기가 0경기 남아있을 때는 어떻게 처리되야 할까요?


    9년 전 link
  • hyunhwan
    hyunhwan

    그리고 추가적으로 적자면


    이 문제는 보다 단순하게 풀 수 있는 방법이 있습니다. 승률을 계산하는 공식을 유심히 보세요.
    그리고 가능한 모든 경우를 헤아리는 것이 아닌, 응원 팀의 최상의 경우만 헤아려 가능여부를 판단할 수 있습니다. 다시 말해서 정말 최상의 조건에서도 진출을 못하는 경우에는 모든 경우에 진출을 하지 못하는 것이고, 또한 적어도 한가지 경우라도 존재할 경웨는 진출 할 수 있는 것이지요.


    9년 전 link
  • bluefa
    bluefa

    소스는 하나의 노드입니다. 경기가 M 개라 한다면

    소스 -> 경기1 , 소스-> 경기2 ... 소스 -> 경기 M 까지 이렇게 간선이 있습니다

    그리고 경기에서 팀으로 가는 간선이 2개가 존재하고요.
    (ex. 경기k --> 팀 1, 팀 2)
    미리 막아놨다는 말은 경기 K 에서 자신이 응원하는 팀으로 가는 용량이

    존재할시에 소스-> 경기 k 로 가는 간선을 0으로 만들어놓았습니다.


    9년 전 link
  • bluefa
    bluefa

    아 그리고 답변 정말 너무 너무 감사합니다. 말씀하신 내용을 전혀 신경쓰지를

    못 했습니다. 정말 감사합니다.


    9년 전 link
  • hyunhwan
    hyunhwan

    maxflow에 대한 궁금한 점을 적자면

    1. 팀 -- 싱크 의 가중치가 1일 경우와 0일 경우는 각각 어떤 경우를 표현하는지 궁금합니다.
    2. 4개의 팀을 선택하는 것은 어떤 기준으로 진행되나요?

    9년 전 link
  • bluefa
    bluefa
    1. 팀 -- 싱크 가중치가 1일 경우에는 해당 팀이 최대 1번까지 이겨도 된다는 의미가 됩니다.. 그리고 0 일경우에는 한번도 이겨서는 안된다라는 의미로 됩니다.

    2.
    8C4 로 미리 vector >combination을 만들어 놓았습니다.

    그러면 70개의 vector 가 만들어집니다. vector 의 크기는 모두

    4이고요. 그리고 여기서 자신이 응원하는 팀이 들어가있을 경우나

    또는 응원하는 팀보다 승률이 낮아질 수가 없는 팀이 들어갈 경우에는

    아예 시작할 수 없게 만들어 놓았습니다.

    --- 그리고 위에서 말씀하신대로 모두다 0 0 0 일때 잘 못된 결과가 나오는 걸 확인했습니다. 정말 감사합니다.


    9년 전 link
  • bluefa
    bluefa

    팀 -- 싱크 가중치는 미리 계산해 놓았고, 자신이 응원하는 팀의 승률보다

    높지않으면서 최대로 이겨도 되는 횟수라고 생각하시면 될 것 같습니다.


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