#P4501. 旅行

    ID: 3738 传统题 1000ms 256MiB 尝试: 317 已通过: 84 难度: 8 上传者: 标签>难度分类提高+/省选-动态规划期望 DPDAG 动态规划图论拓扑排序排序与序列处理二分答案实数二分最小割建模Dinic最大流最小割定理CF2500

旅行

旅行

题目描述

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

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

小 J 是小 C 的好朋友,小 J 可以使用魔法让一些边消失,但是有一些限制 (x,y)(x,y):如果删除第 yy 条边,就必须删除第 xx 条边。所有限制都必须满足。

现在小 J 想知道,在小 C 出发前删去若干条边,使小 C 经过的边数的期望最大。求这个最大期望。

输入格式

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

接下来 mm 行,第 ii 行代表第 ii 条边 x,yx,y,方向是从 xx 到 yy。

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

输出格式

输出一个实数,表示经过的边数的最大期望。与正确答案的绝对误差小于 10−210^{-2} 即可。

样例

3 3 0
1 2
1 3
2 3
2.0000000

数据规模与约定

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

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

1≤n≤501 \le n \le 50,0≤m≤5000 \le m \le 500, 0≤k≤20000 \le k \le 2000。