bzoj#P4501. 旅行

旅行

题目描述

小 C 来到了 F 国,小 C 想好好地参观 F 国。F 国可以看一个有 nn 个点 mm 条边的有向无环图,小 C 刚开始站在 11 号点。假设现在小 C 站在 xx 号点:

  1. xx 没有出边,结束旅游。
  2. xxoo 条出边,小 C 等概率地选一条边走过去。

小 J 是小 C 的好朋友,小 J 可以使用魔法让一些边消失,但是有一些限制 (x,y)(x,y):第 yy 条边如果被删掉了,那么第 xx 条边也会受到影响,导致第 xx 条边被删掉。

现在小 J 想知道,如何删边使得小 C 所经过的边数期望最大。

输入格式

第一行三个整数,n,m,kn,m,k,代表有 nn 个点,mm 条边,kk 个限制。

接下来 mm 行,第 ii 行代表第 ii 条边 x,yx,y,方向是从 xxyy

接下来 kk 行,每行有两个整数 x,yx,y,代表限制。

输出格式

输出一个实数,最大的边数期望。

只要和标准答案误差小于 10210^{-2} 就认为是相同的。

样例输入

3 3 0
1 2
1 3
2 3

样例输出

2.0000000

数据规模与约定

保证图是有向无环的,保证对于每个限制 (x,y)(x,y),第 xx 条边和第 yy 条边的起点是相同的。可能有重边,限制可能重复。

对于每条边 (x,y)(x,y),保证 1x,yn1\le x,y\le n。对于每个限制 (x,y)(x,y),保证 1x,ym1\le x,y\le m

1n501 \le n \le 500m5000 \le m \le 500, 0k20000 \le k \le 2000

题目来源

鸣谢 liuchenrui 提供 SPJ。