Задача . F. Параметрическая циркуляция

Вова недавно познакомился с таким комбинаторным объектом, как циркуляция в графе. Напомним определение: пусть задан ориентированный граф \(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\) это два неотрицательных действительных числа, задающих нижнюю и верхнюю границу для величины циркуляции по ребру \(e\).

Вова полон исследовательского духа, а ещё он не умеет вовремя останавливаться при обдумывании новых тем, с которыми он познакомился. Сейчас он размышляет над следующим естественным вопросом — пусть граф фиксирован, а каждая величина \(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\)-циркуляция?