b058: 3. 關鍵邏輯閘
標籤 :
通過比率 : 78人/83人 ( 94% ) [非即時]
評分方式:
Tolerant

最近更新 : 2007-12-08 07:44

內容
一個組合電路(combinational circuit)由線路(wires)連接一組邏輯閘(logic gates)而成,並且不包含有向迴路(directed cycle)。一個組合電路的效能決定於最後一個主要輸出(primary output)被算出來的時間。假設每一個邏輯閘所需的運算時間都是固定並且是已知的,而線路的延遲(delay)是0。我們希望把一個組合電路所有的關鍵邏輯閘找出來。若一個邏輯閘的運算時間有任何延長,便會影響到整個電路的效能,它就被稱為關鍵邏輯閘。以圖一的組合電路為例,I1、I2、I3是主要輸入;O1、O2是主要輸出;圓圈代表邏輯閘,箭頭代表線路;每個邏輯閘有自己的編號以及固定的延遲時間。在圖一的例子當中,該組合電路中的O1會因為邏輯閘2、4、5的延遲,在時間400才會收到運算結果;而O2會因為邏輯閘2、4、6的延遲,在時間600才收到運算結果,因此O2是最後一個被算出來的主要輸出。關鍵邏輯閘分別是2、4以及6號邏輯閘,當其中一個關鍵邏輯閘的運算時間有任何延長,O2被算出來的時間也會再往後延遲。相反地,就算1號邏輯閘的運算時間從150延長到160,也不會影響到O2被算出來的時間,因此1號邏輯閘並不是關鍵邏輯閘。
輸入說明

第一行為一個整數 n (0 < n < 10000),代表一個組合電路的邏輯閘總數,每個邏輯閘的編號都不同,且範圍是介於 1~n 之間的整數。第二行為一個整數 m (m < 50000),代表線路的總數。接下來的 n 行,依序列出每個邏輯閘的運算時間;每個運算時間的值是介於 0 到 600 之間(含)的整數。最後 m 行,分別列出每一條線路由某個邏輯閘的輸出接到另一個邏輯閘的輸入。
注意:為簡化輸入,我們把主要輸入(primary inputs)與邏輯閘之間的線路,以及邏輯閘與主要輸出(primary outputs)之間的線路省略。(每一個邏輯閘至少都含有一個線路輸出到另一個邏輯閘或主要輸出)

 

輸出說明
列出關鍵邏輯閘的個數。
範例輸入
6
6
150 
200 
150 
100 
100 
300 
1 5 
1 4 
2 4 
4 5 
4 6 
3 6 
5
4
200
200
400
250
200
1 2
3 2
3 5
4 5
範例輸出
3
3
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 10.0s , <1M
提示 :
標籤:
出處:
95學年度全國資訊學科能力競賽


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」