CF1137C Museums Tour
题目描述
一个国家有 $n$ 个城市,通过 $m$ 条单向道路相连。有趣的是,在这个国家,每周有 $d$ 天,并且每个城市恰好有一个博物馆。
已知每个博物馆一周的营业情况(开门或关门)和 $m$ 条单向道路,由于道路的设计,每条道路都需要**恰好一个晚上**的时间通过。你需要设计一条旅游路线,使得从首都:$1$ 号城市开始,并且当天是本周的第一天。每天白天,如果当前城市的博物馆**开着门**,旅行者可以进入博物馆参观展览,否则什么也做不了,这一天的晚上,旅行者要么结束行程,要么通过一条道路前往下一个城市。当然,旅行者**可以多次经过一个城市**。
要求让旅行者能够参观的**不同**博物馆数量尽量多(同一个城市的博物馆参观多次仅算一次),请你求出这个最大值。
输入格式
无
输出格式
无
说明/提示
Explanation of the first example The maximum number of distinct museums to visit is $ 3 $ . It's possible to visit $ 3 $ museums, for example, in the way described below.
- Day 1. Now it's the 1st day of a week, and the tourist is in the city $ 1 $ . The museum there is closed. At night the tourist goes to the city number $ 2 $ .
- Day 2. Now it's the 2nd day of a week, and the tourist is in the city $ 2 $ . The museum there is open, and the tourist visits it. At night the tourist goes to the city number $ 4 $ .
- Day 3. Now it's the 3rd day of a week, and the tourist is in the city $ 4 $ . The museum there is open, and the tourist visits it. At night the tourist goes to the city number $ 1 $ .
- Day 4. Now it's the 1st day of a week, and the tourist is in the city $ 1 $ . The museum there is closed. At night the tourist goes to the city number $ 2 $ .
- Day 5. Now it's the 2nd of a week number $ 2 $ , and the tourist is in the city $ 2 $ . The museum there is open, but the tourist has already visited it. At night the tourist goes to the city number $ 3 $ .
- Day 6. Now it's the 3rd day of a week, and the tourist is in the city $ 3 $ . The museum there is open, and the tourist visits it. After this, the tour is over.
Explanation of the second example The maximum number of distinct museums to visit is $ 2 $ . It's possible to visit $ 2 $ museums, for example, in the way described below.
- Day 1. Now it's the 1st day of a week, and the tourist is in the city $ 1 $ . The museum there is open, and the tourist visits it. At night the tourist goes to the city number $ 2 $ .
- Day 2. Now it's the 2nd day of a week, and the tourist is in the city $ 2 $ . The museum there is closed. At night the tourist goes to the city number $ 3 $ .
- Day 3. Now it's the 3rd day of a week, and the tourist is in the city $ 3 $ . The museum there is open, and the tourist visits it. After this, the tour is over.