白駿1939|重量制限(BFS、二分ナビ)|パイソン


問題のソース:https://www.acmicpc.net/problem/1939


質問する

  • nの島からなる国があります.
  • 人のうち、いくつかの島の間に橋が設置され、車が走ることができる.
  • の2つの島に工場を建てて物品を生産する.
  • 品目を生産する場合、工場で生産した品目を他の工場に運ぶ必要がある.
  • 各ブリッジには
  • 重量制限があります.
  • 重量制限を超えると橋が倒壊します.
  • 一回の移動の中で移動することができる物品の重量の最低価格の
  • を求めます

    入力

  • n:島の数(2<=n<=10000)
  • m:橋数(1<=m<=10000)
  • a,b,c:a号島とb号島の間には、cに制限された重量の橋が存在する.
  • の2つの島の間には複数の橋があります.
  • すべての橋は双方向です.
  • 最後の行は、工場が存在する島の番号を示す2つの異なる整数を与えます.
  • 問題の処理方法


  • この問題のヒントは,ブリッジの重量制限cが10億(10000000)であり,cpuが毎秒約1億個の数を演算できると仮定すると,時間複雑度がO(C)の場合,約10秒かかり,タイムアウトが発生することである.
    したがって,この問題のようにNが非常に大きい場合には,二分探索やパラメータ測定の可能性を考慮すべきであり,時間的複雑度をO(log N)に低減できる.
  • パラメトリック検索とは?


    決定問題(「YES」または「NO」)を最適化アルゴリズムに変換して解決する方法を二分探索を用いる.

  • この問題はパラメトリックメジャーによって
  • は、1回の移動で移動可能な重量(0~10000000)で二分ナビゲーションを行い、
    これは移動可能な重量の最低価格を探す問題です.

  • 初期重量は(開始重量+最大重量)/2に設定します.

  • 移動できる場合は「YES」を返します.
    正解後、重量を増やし、より大きな重量が条件を満たすかどうかを探索します.

  • 移動できない場合は「NO」を返します.
    重量調整後、条件を満たすかどうかを探索します.
  • コード#コード#

    import sys
    from collections import deque
    
    input = sys.stdin.readline
    
    # n : 섬의 개수, m : 도로의 개수, graph = 섬들 간 의 연결 정보
    n, m = map(int, input().split())
    graph = [[] for _ in range(n + 1)]
    
    for _ in range(m):
        island_1, island_2, weight = map(int, input().split())
        graph[island_1].append((island_2, weight))
        graph[island_2].append((island_1, weight))
    
    # 문제에서 주어진 이동 가능한 무게의 최대값, 최솟값
    min_weight = 1
    max_weight = 1000000000
    
    # 시작 도시와 도착 도시 
    start_island, end_island = map(int, input().split())
    
    # BFS 
    # 이동 가능하면 큐에 넣고, 방문
    # 큐에서 꺼낸 도시가 도착도시이면, 방문이 가능하다는 의미이므로 return True
    # 이동이 가능한 도시에 대해서 BFS 탐색을 다 했는데 탐색이 종료되지 않았다면 
        # 종료도시는 무게 제한 때문에 갈 수 없다는 의미이므로 return False
    def bfs(mid_weight):
        queue = deque([start_island])
        visited = set()
        visited.add(start_island)
    
        while queue:
            island = queue.popleft()
            if island == end_island:
                return True
    
            for next, weight in graph[island]:
                if next not in visited and mid_weight <= weight:
                    visited.add(next)
                    queue.append(next)
        
        return False
    
    # 이분 탐색으로 이동 가능한 무게 탐색
    result = min_weight
    
    while min_weight <= max_weight:
        mid = (min_weight + max_weight) // 2
    
        if bfs(mid):
            result = mid
            min_weight = mid + 1
        else:
            max_weight = mid  - 1
    
    print(result)