b328. 災難再臨
Tags : LCA
Accepted rate : 5人/10人 ( 50% ) [非即時]
評分方式:
Tolerant

最近更新 : 2015-07-20 07:04

Content

Background

還記得那些我們曾經歷的災難嗎?PTC201410D!ZJOI 2012 DAY2!如果不記得,請聽我捏造個故事。

Problem

危險種這一類的怪物,不斷地在村莊肆虐作亂,並且不斷地靠近帝國首都,艾斯德斯大人受令狩獵帝國周圍的危險種。

據情報顯示,危險種移動的路徑預估為有向無環圖 (DAG),牠們的數個巢穴坐落於地圖的末端 (也就是不會在有別的地點抵達這個地方),而在首都前將有數個要塞,要塞正牠們的目標之地。為了阻止牠們進入首都,身為艾斯德斯大人的下屬,必須派軍隊前往危險種前往要塞的必經之地。即使抵達的位置無法阻止所有巢穴的危險種,能對艾斯德斯大人貢獻一份心力便已足夠。

由於必經之地很多,好不容易在地圖上標記起來,卻又不知道哪個地點比較好 (可以阻止最多巢穴前往要塞)。正在困擾的同時,艾斯德斯大人已經將危險種剷除。

「一瞬間就將怪物解決,艾斯德斯大人啊!」

儘管艾斯德斯大人解決大部分的危險種,但報告書需要撰寫上呈,請找到至少阻擋一個危險種的埋伏地點數以及一個地點最多能阻擋多少個危險種。

Input

輸入有多組測資。

每組測資第一行會有一個整數 $N$ ($1 \le N \le 32767$)。

接下來會有 $N$ 行,第 $i$ 行上會有數個整數 $x$,直到 $0$ 表示結束,表示有一條邊從 $i \rightarrow x$。

Output
對於每組測資,輸出可以埋伏地點以及埋伏的最佳收穫情況。
Sample Input #1
5
0
1 0
1 0
2 3 0
2 0

17
13 0
9 0
9 14 11 0
10 0
12 0
17 0
0
0
13 14 0
11 0
15 0
15 0
16 0
7 0
16 0
17 0
8 0
Sample Output #1
1 1
8 4
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (50%): 1.0s , <1K
公開 測資點#1 (30%): 1.0s , <1M
公開 測資點#2 (19%): 1.0s , <1M
公開 測資點#3 (1%): 1.0s , <10M
Hint :

範例測資二中

可選地點分別為編號 $V_{9}, \; V_{10}, \; V_{11}, \; V_{12}, \; V_{13}, \; V_{15}, \; V_{16}, \; V_{17} $,而它們分別能抵禦 1, 1, 1, 1, 1, 2, 3, 4 個危險種,巢穴和要塞是不當作為選用的地點。

Tags:
LCA
出處:
PTCZJOI [管理者: morris1028 (碼畜) ]

Status Forum 排行

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