최대가중치-최소가중치를 최소로 하는 (경로와 신장트리)..

  • CYPark
    CYPark
    1. (트리에 포함된 간선의 가중치의 최대값) - (트리에 포함된 간선의 가중치의 최소값)을 최소로 하는 신장트리를 찾고 싶어요..
    2. 위에 문제와 비슷하게.. 그래프가 주어집니다.. 시작점 s, 끝점 t가 주어질때 s->t로 가는 경로에서 (경로에 포함된 간선의 가중치의 최대값) - (경로에 포함된 간선의 가중치의 최소값)을 최소로 하는 경로를 찾고 싶어요.. 2번 문제는 JM님 홈페이지 http://jmk.pe.kr/upload/get/94 의 제일 끝 쪽에 있는 문제인데.. 어떻게 해야될까요..??
      [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    15년 전
5개의 댓글이 있습니다.
  • ibroker
    ibroker

    간선들의 가중치를 모아서 정렬한 다음에 사용할 수 있는 간선 가중치의 범위를 설정합니다.
    그 범위 내에서 답을 구할 수 있으면 범위를 좁히고, 답을 구할 수 없으면 범위를 넓히는 식으로 하면 됩니다.


    15년 전 link
  • CYPark
    CYPark

    음.. 죄송한데 조금만 더 구체적으로 설명해주실수없나요?ㅠㅠ 잘 모르겠어요..ㅜㅜ


    15년 전 link
  • ibroker
    ibroker

    간선 가중치들의 집합을 C={c1, ..., ci, .., cj, .. cn} 라고 합시다.
    현재 선택할 수 있는 간선 가중치의 범위가 ci부터 cj까지라고 하면, 간선의 가중치가 ci~cj사이에 있는
    edge들 만으로 새로운 그래프를 구성합니다.
    이 새로운 그래프에서 1번문제 같은 경우는 spanning tree가 있는지 검사하고, 2번문제 같은 경우는 path가 있는지 조사합니다.
    (즉, 단순히 답이 존재하는지 존재 유무를 결정합니다.)
    만약 답이 존재하지 않는다면 범위를 ci ~ cj+1로 넓히고, 답이 존재한다면 ci+1 ~ cj로 범위를 좁힙니다.
    이런식으로 범위를 넓히거나 좁혀가면서 답을 계속 찾습니다.
    답이 있는 것들 중에서 범위가 제일 좁은 놈을 결과로 출력하면 되겠지요.


    15년 전 link
  • CYPark
    CYPark

    감사합니다.. 그런데 Spanning Tree 일때는 1~n , 2~n ,, 이런식으로 보면 될거같은데 path를 찾을 땐 ci, cj를 어떻게 설정해야 될지 모르겠어요.. ci,cj를 (1,1)로 둬야 되는게 맞겠죠..?


    15년 전 link
  • Toivoa
    Toivoa

    union-find disjoint set을 이용하시면 됩니다. 슬라이드에 있는 문제는 uva에 magic car (http://acm.uva.es/p/v104/10457.html) 와 같은 문제입니다. 경로까지 구하고 싶다면 답이 존재하는 최대/최소 속도를 구한 후에 해당 edge들로만 구성된 graph에서 dijkstra 등을 이용하시면 됩니다.


    15년 전 link

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