j008. 第九題最少通道 - 海青資訊科選手補給站

內容

城市內的水道供應管理，對於每一區市民的用水需求相當重要，但是要能夠在最少的管路需求下達到目的就需要一點技巧。如下圖一為某城市的三個區域水道狀況，其中1區有管道至2 區，2區有管道至3 區。水管道有方向性，因此如果從水庫建造一條水管道至 2 區，1 區就會缺水，所以還需建造另一條水管道至 1 區，這樣一來從水庫到 2 區的水管道就是多餘的了，因為1區可以供應水至 2 區，2 區還可以供應至 3 區，所以最好的狀況就是供應 1 條水管道至 1 區，如圖 2 為最佳狀態。
圖 3 至少需要 2 條水管道，分別至 2 區與 3 區(或 4 區)。
圖 4 只要一條管道至 1 區或 4 區或 5 區即可。

圖一	圖二
圖三	圖四

輸入說明

第一列為 m 個區域 n 個供應管道訊息。(3 ≤ m ≤ 100 , 0 ≤ n ≤ 200)
第二列以後為 n 個供應管道訊息。第一個數字為輸出區，第二個數字為輸入區。
區域編號從 1 開始。

輸出說明

1. 找出從水塔到各區最少的水道數量。並輸出水道至該區的編號。
2. 若管道超過一條，則答案以空白隔開。
3. 若有等效答案，則以區域編號最小者為輸出答案。

範例輸入 #1

3 2
1 2
2 3

範例輸出 #1

範例輸入 #2

範例輸出 #2

2 3

範例輸入 #3

範例輸出 #3

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (20%): 1.0s , <1K
公開測資點#1 (20%): 1.0s , <1K
公開測資點#2 (20%): 1.0s , <1K
公開測資點#3 (20%): 1.0s , <1K
公開測資點#4 (20%): 1.0s , <1K

提示：

標籤:

海青工商資訊科

出處:

113工科賽初賽9 [管理者： zero(管理員) ]

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