1) 問題描述 天然氣經過管道網絡從其生產基地輸送到消耗地，在傳輸過程中，其性能的某一個或幾個方面可能會有所衰減（例如氣壓）。為了保證信號衰減不超過容忍值，應在網絡中的合適位置放置放大器以增加信號（例如電壓）使其與源端相同。設計算法確定把信號放大器放在何處，能使所用的放大器數目最少并且保證信號衰減不超過給定的容忍值。 2) 基本要求 (1) 建立模型，設計數據結構； (2) 設計算法完成放大器的放置； (3) 分析算法的時間復雜度。 3) 設計思想 為了簡化問題，假設分布網絡是二叉樹結構，源端是樹的根結點，信號從一個結點流向其孩子結點，樹中的每一結點（除了根）表示一個可以用來放置放大器的位置。