← 返回题目列表

Codeforces · 925/F

F. 参数循环

中文机器翻译题面 查看原题

Vova 最近了解了图中的循环是什么。回想一下定义:令 $$$G = (V, E)$$$ 为有向图。循环 $$$f$$$ 是非负实数 $$$f_e$$$ ($$$e \in E$$$) 的集合,对于每个顶点 $$$v \in V$$$ ,以下守恒条件成立:

$$$$$$\sum\limits_{e \in \delta^{-}(v)} f_e = \sum\limits_{e \in \delta^{+}(v)} f_e$$$$$$

其中 $$$\delta^{+}(v)$$$ 是在顶点 $$$v$$$ 结束的边集,$$$\delta^{-}(v)$$$ 是在顶点 $$$v$$$ 开始的边集。换句话说,对于每个顶点,总流入流量应等于总流出流量。

令 $$$lr$$$-循环成为这样的循环 $$$f$$$,对于每个边,条件 $$$l_e \leq f_e \leq r_e$$$ 成立,其中每个边 $$$l_e$$$ 和 $$$r_e$$$ 是两个非负实数,表示值的下限和上限该边缘的流通$$$e$$$。

Vova 无法停止思考新主题的应用。现在他思考以下自然问题:让图形固定,每个值 $$$l_e$$$ 和 $$$r_e$$$ 是实数变量 $$$t$$$ 的线性函数:

$$$$$$l_e(t) = a_e t + b_e$$$$$$$$$$$$r_e(t) = c_e t + d_e$$$$$$

请注意,$$$t$$$ 对于所有边都是相同的。

让 $$$t$$$ 从段 $$$[0, 1]$$$ 上的均匀分布中随机选择。图中存在 $$$lr$$$-循环的概率是多少?

输入

第一行包含两个整数 $$$n$$$、$$$m$$$ ($$$1 \leq n \leq 1000$$$、$$$1 \leq m \leq 2000$$$)。

接下来的 $$$m$$$ 行以格式 $$$u_e$$$、$$$v_e$$$、$$$a_e$$$、$$$b_e$$$、$$$c_e$$$、$$$d_e$$$ ($$$1 \leq u_e, v_e \leq n$$$, $$$-10^4 \leq a_e, c_e \leq 10^4$$$, $$$0 \leq b_e, d_e \leq 10^4$$$),其中 $$$u_e$$$ 和 $$$v_e$$$ 是边 $$$e$$$ 的起点和终点,其余 4 个整数描述循环上下界的线性函数。

保证对于任何 $$$t \in [0, 1]$$$ 和任何边 $$$e \in E$$$,以下条件成立 $$$0 \leq l_e(t) \leq r_e(t) \leq 10^4$$$。

输出

打印单个实数 - 图中存在 $$$lr$$$ 循环的概率,假设 $$$t$$$ 是从 $$$[0, 1]$$$ 段中均匀随机选择的。如果您的答案与陪审团答案的绝对差异不大于 $$$10^{-6}$$$,则视为正确。

示例

输入 #1

3 3
1 2 0 3 -4 7
2 3 -2 5 1 6
3 1 0 4 0 4

输出 #1

0.25

注意

在第一个示例中,守恒条件仅允许所有三个边具有相等值 $$$f_e$$$ 的循环。无论选择 $$$t$$$,最后一条边上的循环值应为 $$$4$$$,因此概率为

$$$$$$P(4 \in [3, -4t + 7]~~\&~~4 \in [-2t + 5, t + 6]) = 0.25$$$$$$