e999: 巨額獎金(Bonus)
Tags :
Accepted rate : 18人/19人 ( 95% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-04-30 15:47

Content

某戀愛遊戲製作公司為了慶祝十周年,特別在網路上發布了一個遊戲,誰能通關拿到最佳結局,就能拿到新台幣一千萬的巨額獎金。遊戲的內容如下:

一個男孩遇見了心儀的對象,參賽者要幫助這個男孩在每個階段進行事件選擇,選擇後會進入下一個階段,然後再進行選擇……直至結局階段。結局為何,取決於玩家所經歷的階段和事件。所有的結局中,只有一個路線能達成最佳結局。

礙於成本考量,公司決定對於每個報名的人收費。他們對收費的金額進行討論,最後討論出了一連串複雜的數學式子作為費用的計算公式,其中遊戲進行的總路線數是最關鍵的數值。你是公司的一名員工,你必須負責算出路線總數R。

遊戲的設定如下:

一、遊戲共有N個階段,S0為初始階段,SN-1為結局階段。

二、對每個階段Si,事件Eij會讓玩家進入到階段Sj。

三、對於任意階段,玩家最多僅能經歷一次。
即:不會有任何事件可以讓玩家回到曾經經歷過的階段。

四、不管中間的事件選擇是什麼,總是S0開始,SN-1結束。

五、路線總數R不為0。

六、不會有重複的事件(兩個階段至多只由一個事件連接)。

 

以上圖為例,這個遊戲共有7個不同路線可以到達Sn-1,

(1) 0 → 1 → 3 → 9

(2) 0 → 1 → 4 → 9

(3) 0 → 1 → 5 → 9

(4) 0 → 1 → 6 → 7 → 9

(5) 0 → 1 → 6 → 8 → 9

(6) 0 → 2 → 6 → 7 → 9

(7) 0 → 2 → 6 → 8 → 9

Input

每組測資第一列有兩個正整數S及E,S表示階段的數量(2≤S≤100),階段分別編號0至S-1,E為事件的數量(S-1≤E≤2×S)。接著有E列,每列有兩個整數i、j,表示階段Si存在事件Eij能讓玩家進入階段Sj。

Output

每組測資輸出一個正整數R,為路線總數。

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

不准作弊!

改編自2019年5月TOI練習賽潛力組

Tags:
出處:
Caido2019學年度下學期延平中學國中組校內程式設計競賽 [管理者:
becaido (Caido)
]


ID User Problem Subject Hit Post Date
21227
s810617@gm.c... (Brian)
e999
演算法提示
60 2020-05-04 14:05