d105: P-8-5. 自動分裝 (APCS202002)
Tags : 圖論
Accepted rate : 48人/51人 ( 94% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-05-20 09:42

Content

某工程公司設計了一個自動分裝的系統。貨物會一個一個的被送進此系統,經過一些

切換器的轉送後,會被輸送到 n 個貨箱。系統有 n-1 個切換器與 n 個貨箱。每個切

換器有一個入口以及左右兩個出口,切換器的出口會接到其他切換器或是連接到貨

箱,貨箱則只有入口。

下圖是一個 n=7 的例子,圓代表切換器,方形代表貨箱,請注 意編號 1 ~ n–1 的裝置是切換器,貨箱編號是 n ~ 2n–1,且貨物入口一定是 1 號切換器的入口。

每一個切換器會分別記錄左右兩個出口所通往貨箱的總重量,當貨物進入此切換器

時,切換器會將貨物轉送到「貨箱總重量比較輕的那個出口」,如果兩邊一樣重,則

送往左邊。貨物進入貨箱後就存放在該貨箱,該貨物

的重量就會加入該貨箱的總重,因此可能影響下一個貨物的運送路徑。

輸入此系統的連接架構與貨箱目前的重量,以及接下來依序進入的 m 個貨物的重量,

請計算這 m 個貨物分別會被送到哪一個貨箱。

 

Input

第一行為兩個正整數 n 和 m,其中 n <= 1e5 且 m <= 100。

第二行有 n 個非負整數,依序是編號為 n ~ 2n-1 各個貨箱初始的重量。

第三行是 m 個正整數,代表接下來依序進入的貨物重量。全部貨箱初始的重量與貨物重量總和不會超過 $10^9$。

第四行開始有 n-1 行,這些是系統架構的資訊:每一行有三個整數 p、s 與 t,

代表裝置 p 的左右出口分別接到裝置 s 與 t,其中 p 一定是一個切換器的編號(1<=p

<n)。同一行數字之間以空白間隔。

Output

輸出一行有 m 個整數,依序代表接下來進入系統的 m 個貨物所進入到的貨箱編

號,數字之間以一個空白間隔。

Sample Input
// 1
4 5
0 0 0 0
5 3 4 2 1
1 2 3
2 4 5
3 6 7
// 2
7 2
9 2 1 6 8 7 5
2 3
1 2 5
2 3 7
3 13 10
4 11 9
6 12 8
5 6 4
Sample Output
// 1
4 6 7 5 5
// 2
8 7
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <10M
公開 測資點#3 (20%): 1.0s , <10M
公開 測資點#4 (20%): 1.0s , <10M
Hint :

以上圖的例子來說,假設每一個貨箱目前的重量如各矩形下方的標示,下 一個到達的貨物的運送過程如下:一號切換器左邊出口是連到 {13, 10, 7} 三個貨箱,目前總重5+6+9=20;右邊出口連到的是 {12, 8, 11, 9} 四個貨箱,目 前總重 7+2+8+1=18,因此貨物會由右邊出口送到 5 號切換器。5 號切換器的左邊與 右邊的貨箱總重是一樣的(7+2=8+1),因此貨物由左出口送至 6 號切換器。最後, 6 號切換器將貨物送到 8 號貨箱(7>2)。貨物進入貨箱後就存放在該貨箱,該貨物 的重量就會加入該貨箱的總重,因此可能影響下一個貨物的運送路徑。

Tags:
圖論
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\ \mathtt{Comp.}\ \&\ \mathsf{Info.}\ \mathit{Club}$)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」