CF925F Parametric Circulation

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 \in 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$ 的起点和终点，后四个整数描述该边上环流上下界的线性函数。 保证对于任意 $t \in [0, 1]$ 和任意边 $e \in E$，都有 $0 \leq l_e(t) \leq r_e(t) \leq 10^4$。

输出一个实数，表示当 $t$ 从区间 $[0, 1]$ 上均匀随机选取时，存在 $lr$-环流的概率。只要你的答案与标准答案的绝对误差不超过 $10^{-6}$，就视为正确。

在第一个样例中，守恒条件只允许所有三条边的流量 $f_e$ 相等。最后一条边的流量无论 $t$ 取何值都必须为 $4$，因此概率为 $$ P(4 \in [3, -4t + 7]~~\&~~4 \in [-2t + 5, t + 6]) = 0.25 $$ 由 ChatGPT 4.1 翻译