bzoj#P4501. 旅行
旅行
题目描述
小 C 来到了 F 国,小 C 想好好地参观 F 国。F 国可以看一个有 个点 条边的有向无环图,小 C 刚开始站在 号点。假设现在小 C 站在 号点:
- 点 没有出边,结束旅游。
- 点 有 条出边,小 C 等概率地选一条边走过去。
小 J 是小 C 的好朋友,小 J 可以使用魔法让一些边消失,但是有一些限制 :第 条边如果被删掉了,那么第 条边也会受到影响,导致第 条边被删掉。
现在小 J 想知道,如何删边使得小 C 所经过的边数期望最大。
输入格式
第一行三个整数,,代表有 个点, 条边, 个限制。
接下来 行,第 行代表第 条边 ,方向是从 到 。
接下来 行,每行有两个整数 ,代表限制。
输出格式
输出一个实数,最大的边数期望。
只要和标准答案误差小于 就认为是相同的。
样例输入
3 3 0
1 2
1 3
2 3
样例输出
2.0000000
数据规模与约定
保证图是有向无环的,保证对于每个限制 ,第 条边和第 条边的起点是相同的。可能有重边,限制可能重复。
对于每条边 ,保证 。对于每个限制 ,保证 。
,, 。
题目来源
鸣谢 liuchenrui 提供 SPJ。