[editorial] 2009 Phuket Regional - K. Highway Patrol

  • Neon
    Neon

    원문은 역시나 제 springnote에 있습니다.
    개요

    • irc.hanirc.org #icpc에서 1주1셋돌기로 대회할 때 풀어본 문제.
    • 실제 대회에선 푼 팀이 없었다.
    • 아이디어가 꽤... 괜찮았다고 자평함

    풀이

    • 들어오는 patrol의 수와 나가는 patrol의 수가 같다 -> 모든 경로는 어떤 cycle의 일부여야 한다.
      • 음... 대회 당시에는 얼핏 이런 정도의 아이디어로만 생각하고 말았기 때문에 자세한 증명을 적기는 좀 어렵다.
    • 무조건 연결해야 하는 edge들이 있는데, 아무렇게나 이런 edge들을 포함하는 cycle들을 찾은 다음에 해를 개선하는 방법으로 접근해보기로 했다.
      <ul><li>※ : 어떤 해를 표현하는 방법은&nbsp;patrol이 다니는 edge들의 집합으로 정의하겠다. 예) S={1,2,5} : 1,2,5번 edge에 patrol이 지나고, 나머지 edge는 감시카메라를 놓는 해.
      </li><li>임의의 해 S를 개선하기 위해서는 S에 새로운 cycle을 추가하거나, 기존의 cycle을 변형해서 새로운 cycle을 만들 수 있으면 되는데, 기존의 cycle을 변형하는 방법은...
      <ul><li> network flow의 idea를 응용하면 된다. 어떤 edge E가 사용중이라면 E의 끝점에서 E의 시작점으로 이동하는 가상의 edge가 있다고 가정할 수 있는 것이다.
      <ul><li>다만 이 방법을 사용할 때, 무조건 연결해야 하는 edge들을 연결해제하면 안되니 특수처리해주는 센스가 필요함.
      </li></ul>
    • 그러므로 해를 개선하는(=negative 가중치의) cycle을 찾으면 되니 bellman-ford 알고리즘을 사용해서 계속해서 해를 개선하면 된다.
      <ul><li>다만... 계속해서 해를 개선하는 local search 방식이기 때문에 local minimum인 경우가 존재한다면 조금 문제가 된다. 증명해야 하는데 대회 당시에는 그런거 안함 ㅋ
      </li></ul>
    • 이런 식으로 최적해를 찾았는데, 최적해에 patrol이 하나도 없으면 문제 조건 때문에 안되므로, 가장 작은 가중치의 cycle을 하나 찾아서 집어넣는다.

    • 참고자료
      [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]


      9년 전
0개의 댓글이 있습니다.
  • 댓글을 남기시려면 로그인하세요.