2006년 ICPC 서울 본선 J번 문제 어떻게 푸나여?

  • dgsquare
    dgsquare

    안녕하세요.
    눈팅을 주로하는 탑코더 Rating 800점대의 유저입니다. :-)
    다름이 아니라 최근 알고리즘 공부겸 예전 ICPC 문제를 풀고있는데여.
    2006년 문제를 푸는 중 J번에서 난관에 부딧혀 질문을 올립니다.
    경로는 여기구여,
    http://acm.kaist.ac.kr/Problems/2006j.pdf
    대충 요약해보면 건널 수 있는 통나무의 최대치를 구하되,
    1. 시작 통나무와 마지막 통나무가 동일해야하며
    2. 통나무는 한번씩만 건널 수 있으며
    3. 통나무는 겹치는 영역이 존재시 수작으로 이동할 수 있다는 것입니다.
    저는 이 문제를 건널 수 있는 통나무들을 edge로 구성한 뒤, 최대 Cycle을 구하면 풀 수 있다고 생각했는데요.
    Cut Vertex를 구하는 방식을 응용하면 최대 Cycle을 찾을 수 있다고 생각했는데, 이부분에 아이디어가 잘 안떠오르네요.
    제 방법이 맞는지, 아니면 다른 간단한 방법이 있는지 알고 싶습니다.
    그리고 그래프에서 최대 Cycle을 구하는 방식을 알 수 있을까요?

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


    13년 전
2개의 댓글이 있습니다.
  • iddaga
    iddaga

    저 경우는 일반그래프가 아니라 1차원 구간으로 만들어진 그래프라서 최대 Cycle 구하는 방법이 따로 있을걸요 ;


    13년 전 link
  • dgsquare
    dgsquare

    그런가여? 제가 방법을 잘 몰라서 그러는데, 혹시 관련 레퍼런스를 구할 수 있는 곳이 없을까여? ;;


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