Skip to content

14169: 【原4169】旅行

题目

题目描述

author: Sakiko 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4169

Description

侯不会来到了F国,侯不会想好好地参观F国。F国可以看一个有\(n\)个点\(m\)条边的有向无环图,侯不会刚开始站在\(1\)号点。假设现在侯不会站在\(x\)号点: 1. 点\(x\)没有出边,结束旅游。 2. 点\(x\)有\(o\)条出边,侯不会等概率地选一条边走过去。

苏前端是侯不会的好朋友,苏前端可以使用魔法让一些边消失,但是有一些限制\((x,y)\):第\(y\)条边如果被删掉了,那么第\(x\)条边也会受到影响,导致第\(x\)条边被删掉。 现在苏前端想知道,如何删边使得侯不会所经过的边数期望最大。

Input Format

第一行三个整数,\(n,m,k\),代表有\(n\)个点,\(m\)条边,\(k\)个限制。点和边的编号都是从\(1\)开始。 接下来\(m\)行,第i行代表第i条边\(x,y\),方向是从\(x\)到\(y\)。 接下来\(k\)行,每行有两个整数\(x,y\),代表限制。

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

Output Format

输出一个实数,最大的边数期望。只要和标准答案误差小于\(10^{-2}\)就认为是相同的。

Sample1 Input

3 3 0
1 2
1 3
2 3

Sample1 Output

2.0000000

Sample2 Input

3 3 1
1 2
1 3
2 3
1 2

Sample2 Output

1.50000000000

Data Range

30% :\(m <= 20\) 60% :边是随机生成的。 100% :\(1 <= n <= 50, 0 <= m <= 500, 0 <= k <= 2000\)

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!