English · Original
Chinese · Translation
Formal · Original
Vova has recently learned what a _circulaton_ in a graph is. Recall the definition: let $G = (V, E)$ be a directed graph. A circulation $f$ is such a collection of non-negative real numbers $f_e$ ($e \in E$), that for each vertex $v \in V$ the following _conservation_ condition holds:
\\sum\\limits_{e \\in \\delta^{-}(v)} f_e = \\sum\\limits_{e \\in \\delta^{+}(v)} f_e
where $\delta^{+}(v)$ is the set of edges that end in the vertex $v$, and $\delta^{-}(v)$ is the set of edges that start in the vertex $v$. In other words, for each vertex the total incoming flow should be equal to the total outcoming flow.
Let a $lr$\-circulation be such a circulation $f$ that for each edge the condition $l_e \leq f_e \leq r_e$ holds, where $l_e$ and $r_e$ for each edge $e \in E$ are two non-negative real numbers denoting the lower and upper bounds on the value of the circulation on this edge $e$.
Vova can't stop thinking about applications of a new topic. Right now he thinks about the following _natural_ question: let the graph be fixed, and each value $l_e$ and $r_e$ be a linear function of a real variable $t$:
l_e(t) = a_e t + b_e r_e(t) = c_e t + d_e
Note that $t$ is the **same** for all edges.
Let $t$ be chosen at random from uniform distribution on a segment $[0, 1]$. What is the probability of existence of $lr$\-circulation in the graph?
## Input
The first line contains two integers $n$, $m$ ($1 \leq n \leq 1000$, $1 \leq m \leq 2000$).
Each of the next $m$ lines describes edges of the graph in the format $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$), where $u_e$ and $v_e$ are the startpoint and the endpoint of the edge $e$, and the remaining 4 integers describe the linear functions for the upper and lower bound of circulation.
It is guaranteed that for any $t \in [0, 1]$ and for any edge $e \in E$ the following condition holds $0 \leq l_e(t) \leq r_e(t) \leq 10^4$.
## Output
Print a single real integer — the probability of existence of $lr$\-circulation in the graph, given that $t$ is chosen uniformly at random from the segment $[0, 1]$. Your answer is considered correct if its absolute difference from jury's answer is not greater than $10^{-6}$.
[samples]
## Note
In the first example the conservation condition allows only circulations with equal values $f_e$ for all three edges. The value of circulation on the last edge should be $4$ whatever $t$ is chosen, so the probability is
P(4 \\in \[3, -4t + 7\]~~\\&~~4 \\in \[-2t + 5, t + 6\]) = 0.25
Vova 最近学习了图中的 _循环_（circulation）是什么。回顾定义：设 $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$ 为起点的边的集合。换句话说，对每个顶点，总流入流量应等于总流出流量。
定义一个 $l$-$r$-循环为这样的循环 $f$，使得对每条边 $e \in E$，满足条件 $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]$ 上的均匀分布中随机选取。求图中存在 $l$-$r$-循环的概率是多少？
第一行包含两个整数 $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]$ 上均匀随机选取时，图中存在 $l$-$r$-循环的概率。你的答案若与标准答案的绝对误差不超过 $10^{-6}$，则被视为正确。
在第一个例子中，守恒条件仅允许所有三条边上的循环值相等。无论 $t$ 取何值，最后一条边上的循环值必须为 $4$，因此概率为
$$P(4 \in [3, -4t + 7]~~\&~~4 \in [-2t + 5, t + 6]) = 0.25$$
## Input
第一行包含两个整数 $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$。
## Output
输出一个实数——在 $t$ 从区间 $[0, 1]$ 上均匀随机选取时，图中存在 $l$-$r$-循环的概率。你的答案若与标准答案的绝对误差不超过 $10^{-6}$，则被视为正确。
[samples]
## Note
在第一个例子中，守恒条件仅允许所有三条边上的循环值相等。无论 $t$ 取何值，最后一条边上的循环值必须为 $4$，因此概率为$$P(4 \in [3, -4t + 7]~~\&~~4 \in [-2t + 5, t + 6]) = 0.25$$
**Definitions**
Let $ G = (V, E) $ be a directed graph with $ n = |V| $, $ m = |E| $.
For each edge $ e \in E $, let:
- $ u_e, v_e \in V $ denote the tail and head of $ e $,
- $ l_e(t) = a_e t + b_e $ be the lower bound,
- $ r_e(t) = c_e t + d_e $ be the upper bound,
where $ t \in [0, 1] $ is a real parameter.
Let $ f_e(t) \in \mathbb{R}_{\geq 0} $ denote the flow on edge $ e $ at parameter $ t $.
A function $ f(t) = (f_e(t))_{e \in E} $ is an $ l_r $-circulation at $ t $ if:
1. **Flow conservation**: For each vertex $ v \in V $,
$$
\sum_{e \in \delta^-(v)} f_e(t) = \sum_{e \in \delta^+(v)} f_e(t),
$$
2. **Capacity constraints**: For each edge $ e \in E $,
$$
l_e(t) \leq f_e(t) \leq r_e(t).
$$
**Constraints**
1. $ 1 \leq n \leq 1000 $, $ 1 \leq m \leq 2000 $.
2. For all $ e \in E $, $ a_e, c_e \in [-10^4, 10^4] $, $ b_e, d_e \in [0, 10^4] $.
3. For all $ t \in [0,1] $ and all $ e \in E $, $ 0 \leq l_e(t) \leq r_e(t) \leq 10^4 $.
**Objective**
Compute the probability that a random $ t \sim \text{Uniform}[0,1] $ admits at least one $ l_r $-circulation:
$$
\mathbb{P}\left( \exists f: \text{flow conservation} \land \forall e \in E,\ l_e(t) \leq f_e \leq r_e(t) \right)
$$
Equivalently, compute the Lebesgue measure of the set:
$$
\left\{ t \in [0,1] \ \middle| \ \exists f \in \mathbb{R}^m_{\geq 0} \text{ s.t. } A f = 0 \text{ and } l(t) \leq f \leq r(t) \right\},
$$
where $ A \in \mathbb{R}^{n \times m} $ is the vertex-edge incidence matrix (with rows indexed by vertices, columns by edges, and entries $ +1 $ for tail, $ -1 $ for head, $ 0 $ otherwise), and $ l(t), r(t) \in \mathbb{R}^m $ are vectors of lower and upper bounds as functions of $ t $.
API Response (JSON)
{
"problem": {
"name": "F. Parametric Circulation",
"description": {
"content": "Vova has recently learned what a _circulaton_ in a graph is. Recall the definition: let $G = (V, E)$ be a directed graph. A circulation $f$ is such a collection of non-negative real numbers $f_e$ ($e ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF966F"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Vova has recently learned what a _circulaton_ in a graph is. Recall the definition: let $G = (V, E)$ be a directed graph. A circulation $f$ is such a collection of non-negative real numbers $f_e$ ($e ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Vova 最近学习了图中的 _循环_（circulation）是什么。回顾定义：设 $G = (V, E)$ 为一个有向图。一个循环 $f$ 是一组非负实数 $f_e$（$e \\in E$），使得对每个顶点 $v \\in V$，满足以下 _守恒_ 条件：\n\n$$\\sum\\limits_{e \\in \\delta^{-}(v)} f_e = \\sum\\limits_{e \\in \\delta^{+}...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ G = (V, E) $ be a directed graph with $ n = |V| $, $ m = |E| $. \nFor each edge $ e \\in E $, let: \n- $ u_e, v_e \\in V $ denote the tail and head of $ e $, \n- $ l_e(t) = a_e t...",
"is_translate": false,
"language": "Formal"
}
]
}