{"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 \\in E$), that for each vertex $v \\in V$ the following _conservation_ condition holds:\n\n\\\\sum\\\\limits_{e \\\\in \\\\delta^{-}(v)} f_e = \\\\sum\\\\limits_{e \\\\in \\\\delta^{+}(v)} f_e\n\nwhere $\\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.\n\nLet 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$.\n\nVova 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$:\n\nl_e(t) = a_e t + b_e r_e(t) = c_e t + d_e\n\nNote that $t$ is the **same** for all edges.\n\nLet $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?\n\n## Input\n\nThe first line contains two integers $n$, $m$ ($1 \\leq n \\leq 1000$, $1 \\leq m \\leq 2000$).\n\nEach 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.\n\nIt 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$.\n\n## Output\n\nPrint 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}$.\n\n[samples]\n\n## Note\n\nIn 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\n\nP(4 \\\\in \\[3, -4t + 7\\]~~\\\\&~~4 \\\\in \\[-2t + 5, t + 6\\]) = 0.25","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^{+}(v)} f_e$$\n\n其中 $\\delta^{+}(v)$ 是所有以 $v$ 为终点的边的集合，$\\delta^{-}(v)$ 是所有以 $v$ 为起点的边的集合。换句话说，对每个顶点，总流入流量应等于总流出流量。\n\n定义一个 $l$-$r$-循环为这样的循环 $f$，使得对每条边 $e \\in E$，满足条件 $l_e \\leq f_e \\leq r_e$，其中 $l_e$ 和 $r_e$ 是每条边 $e \\in E$ 上的两个非负实数，分别表示该边上循环值的下界和上界。\n\nVova 无法停止思考这一新主题的应用。现在他思考这样一个 _自然_ 的问题：设图是固定的，每条边的 $l_e$ 和 $r_e$ 都是实变量 $t$ 的线性函数：\n\n$$l_e(t) = a_e t + b_e$$ $$r_e(t) = c_e t + d_e$$\n\n注意，$t$ 对所有边是 _相同的_。\n\n设 $t$ 从区间 $[0, 1]$ 上的均匀分布中随机选取。求图中存在 $l$-$r$-循环的概率是多少？\n\n第一行包含两个整数 $n$，$m$（$1 \\leq n \\leq 1000$，$1 \\leq m \\leq 2000$）。\n\n接下来的 $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$ 的起点和终点，其余四个整数描述该边上循环值的上界和下界的线性函数。\n\n保证对于任意 $t \\in [0, 1]$ 和任意边 $e \\in E$，都有 $0 \\leq l_e(t) \\leq r_e(t) \\leq 10^4$。\n\n输出一个实数——在 $t$ 从区间 $[0, 1]$ 上均匀随机选取时，图中存在 $l$-$r$-循环的概率。你的答案若与标准答案的绝对误差不超过 $10^{-6}$，则被视为正确。\n\n在第一个例子中，守恒条件仅允许所有三条边上的循环值相等。无论 $t$ 取何值，最后一条边上的循环值必须为 $4$，因此概率为\n\n$$P(4 \\in [3, -4t + 7]~~\\&~~4 \\in [-2t + 5, t + 6]) = 0.25$$\n\n## Input\n\n第一行包含两个整数 $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$。\n\n## Output\n\n输出一个实数——在 $t$ 从区间 $[0, 1]$ 上均匀随机选取时，图中存在 $l$-$r$-循环的概率。你的答案若与标准答案的绝对误差不超过 $10^{-6}$，则被视为正确。\n\n[samples]\n\n## Note\n\n在第一个例子中，守恒条件仅允许所有三条边上的循环值相等。无论 $t$ 取何值，最后一条边上的循环值必须为 $4$，因此概率为$$P(4 \\in [3, -4t + 7]~~\\&~~4 \\in [-2t + 5, t + 6]) = 0.25$$","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 + b_e $ be the lower bound,  \n- $ r_e(t) = c_e t + d_e $ be the upper bound,  \nwhere $ t \\in [0, 1] $ is a real parameter.\n\nLet $ f_e(t) \\in \\mathbb{R}_{\\geq 0} $ denote the flow on edge $ e $ at parameter $ t $.  \n\nA function $ f(t) = (f_e(t))_{e \\in E} $ is an $ l_r $-circulation at $ t $ if:  \n1. **Flow conservation**: For each vertex $ v \\in V $,  \n   $$\n   \\sum_{e \\in \\delta^-(v)} f_e(t) = \\sum_{e \\in \\delta^+(v)} f_e(t),\n   $$  \n2. **Capacity constraints**: For each edge $ e \\in E $,  \n   $$\n   l_e(t) \\leq f_e(t) \\leq r_e(t).\n   $$\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 1000 $, $ 1 \\leq m \\leq 2000 $.  \n2. For all $ e \\in E $, $ a_e, c_e \\in [-10^4, 10^4] $, $ b_e, d_e \\in [0, 10^4] $.  \n3. For all $ t \\in [0,1] $ and all $ e \\in E $, $ 0 \\leq l_e(t) \\leq r_e(t) \\leq 10^4 $.  \n\n**Objective**  \nCompute the probability that a random $ t \\sim \\text{Uniform}[0,1] $ admits at least one $ l_r $-circulation:  \n$$\n\\mathbb{P}\\left( \\exists f: \\text{flow conservation} \\land \\forall e \\in E,\\ l_e(t) \\leq f_e \\leq r_e(t) \\right)\n$$  \nEquivalently, compute the Lebesgue measure of the set:  \n$$\n\\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\\},\n$$  \nwhere $ 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 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF966F","tags":["flows"],"sample_group":[["3 3\n1 2 0 3 -4 7\n2 3 -2 5 1 6\n3 1 0 4 0 4","0.25"]],"created_at":"2026-03-03 11:00:39"}}