TopCoder

Thumb 1800
weyryafjnm;
erfvjuaweikm

User's AC Ratio

93.8% (30/32)

Submission's AC Ratio

57.3% (67/117)

Description

  自從黑色騎士團上次的最終野望被白色騎士豬殺苦破滅之後,黑色騎士團銷聲滅跡了一陣子,不過他們仍繼續計畫著侵略神聖的大不列顛帝國。

  終於他們發現了一個機會:原來大不列顛帝國的命脈就是對外輸出的藥品”REBRAIN”,只要能控制住它所有加工地點之間的交通道路,那大不列顛帝國就完了!

  與之前一樣,他們只要佔領一個據點就可以控制與他相鄰的道路了!

  ”REBRAIN”的運輸過程十分有趣,他有一個總工廠來製造”REBRAIN”的一些半成品,再依序經過幾個有向道路到下個加工地點進行加工,就這樣一直到完成成品,並且為了不讓產品流程出問題,他們的運輸路徑不會出現環狀或逆向的情況,而且由總工廠開始到每個加工地點都有恰好一種原料運輸的路徑

  不過黑色騎士團的人手有限,所以他們希望佔據最少的據點就可以完全控制整個運輸途徑。

Input Format

本題有只有一筆測試資料

每筆測試資料的

第一行有一個數字 $n$,代表有 $n$ 個加工點(從 $0$ 號編號至 $n-1$ 號,$0$ 號為總工廠),$n \le 32768$

第二行開始有 $n$ 行,會有一個數字 $m_i$ 代表第 $i$ 個工廠的下游有幾個工廠,接下來以空白分隔 $m_i$ 個數字,代表其下游的工廠編號

Output Format

對每筆資料輸出一個數字 $k$,代表最少佔據 $k$ 個據點才能達到逆襲野望

Sample Input

4
1 1
2 2 3
0
0

Sample Output

1

Hints

Problem Source

原TIOJ1394 / 快樂暑假營第三次練習比賽。
Problem Setter:hallogameboy

Subtasks

No. Testdata Range Score
1 0 25
2 1 25
3 2 25
4 3 25

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 999 131072 262144 1
1 999 131072 262144 2
2 999 131072 262144 3
3 999 131072 262144 4