Parametric Circulation
Contest: VK Cup 2018 - Round 3
Difficulty rating: 3100
Tags: binary search, flows

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 format:
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 format:
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}$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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$$$$$$

Example input:
3 3
1 2 0 3 -4 7
2 3 -2 5 1 6
3 1 0 4 0 4

Example output:
0.25

Editorial:
First, let's use the classical reduction of $$$lr$$$-circulation problem to the maximum flow problem. Consider a network $$$G' = (V \cup \{s, t\}, E')$$$ where for each $$$e = uv \in E$$$ there are three edges:
• $$$e_0 = uv$$$ with capacity $$$c_{e_0} = r_e - l_e$$$
• $$$e_1 = sv$$$ with capacity $$$c_{e_1} = l_e$$$
• $$$e_2 = ut$$$ with capacity $$$c_{e_2} = l_e$$$
Statement: it is possible to provide a bisection between $$$s-t$$$ flows of value $$$\sum \limits_{e \in E} l_e$$$ in $$$G'$$$ and $$$lr$$$-circulations in $$$G$$$. Indeed, consider a flow $$$f'$$$ in $$$G'$$$, that saturates all edges going from $$$s$$$ (and all the edges leading into $$$t$$$ at the same time). Let $$$f_e = f'_{e_0} + l_e$$$. Notice that it is a correct circulation: for any vertex $$$v$$$
$$$$$$\sum\limits_{e \in \delta^{+}(v)} f_{e} = \sum\limits_{e \in \delta^{+}(v)} f'_{e_0} + \sum\limits_{e \in \delta^{+}} l_e = \sum\limits_{e \in \delta^{+}(v)} f'_{e_0} + \sum\limits_{e \in \delta^{+}} f_{e_1} = \sum\limits_{e \in \delta^{-}(v)} f'_{e_0} + \sum\limits_{e \in \delta^{-}} f_{e_2} = \sum\limits_{e \in \delta^{-}(v)} f'_{e_0} + \sum\limits_{e \in \delta^{-}} l_e = \sum\limits_{e \in \delta^{-}(v)} f_{e}$$$$$$
where the middle equation is immediately following from the conservation condition for any vertex from $$$V$$$ for a flow $$$f'$$$.
On the other hand, the obtained circulation is indeed an $$$lr$$$-circulation because of how we got values of $$$f'_e$$$. By performing all the steps in the reverse direction, we may recover a maximum flow in $$$G'$$$ by any $$$lr$$$-circulation that finishes our proof.
Now we are going to answer the following question: we have a parametric network $$$G'(t)$$$ in which all capacities linearly depend on $$$t$$$, we have to find the probability that $$$G'$$$ allows a flow that saturates all edges from the source under condition that $$$t$$$ is sampled from $$$U[0, 1]$$$.
Let us show that the set of $$$t$$$ that allow existence of a sought flow is a segment. It follows from the fact that the value $$$maxflow(t)$$$ of a maximum flow in $$$G'(t)$$$ is concave: suppose $$$f'(t_1)$$$ is a an admissible flow in $$$G'(t_1)$$$ and $$$f'(t_2)$$$ is an admissible flow in $$$G'_{t_2}$$$. Then it is easy to see that $$$\lambda f'(t_1) + (1 - \lambda) f'(t_2)$$$ is an admissible flow in $$$G'\left(\lambda t_1 + (1 - \lambda) t_2\right)$$$ for any $$$\lambda \in [0, 1]$$$ (as all the constraints on variables $$$f'_{e}$$$ are linear inequalities), from which immediately follows that $$$maxflow(\lambda t_1 + (1 - \lambda) t_2) \geq \lambda maxflow(t_1) + (1 - \lambda) maxflow(t_2)$$$.
Denote $$$suml(t) = \sum\limits_{e \in E}l(t)$$$. Let us notices that $$$gap(t) = suml(t) - maxflow(t) \geq 0$$$ for any $$$t$$$ and we are interested in precisely those values of $$$t$$$, such that $$$gap(t) = 0$$$. Thus, the sought values of $$$t$$$ form a segment as the function $$$gap(t)$$$ is convex.
The remaining part of the solution is very simple: find a minimum of a convexvalue $$$gap(t)$$$ over a segment $$$[0, 1]$$$. If it is non-zero, then the answer is 0. Otherwise, we can locate the boundaries of an answer segment using two binary searches and print the difference between them.
While implementing such a solution, one may face several difficulties arising from the precision issues, so we will provide two observations that may help you deal with them.
One may notice that $$$maxflow(t)$$$ is actually a piecewise linear function, all pieces of which have the integer slope. Actually, $$$maxflow(t) = mincut(t) = \min\limits_{\text{cut }C} cost(C, t)$$$, and the cost of any fixed cut in $$$G'(t)$$$ is a linear function of $$$t$$$ with an integer slope. Thus, $$$maxflow(t)$$$ is a lower envelope of a family of linear functions with integer slopes. The similar fact holds for a function $$$gap(t)$$$ also. And we are interested in a horizontal segment in $$$gap(t)$$$ which may be found using the binary search over a sign of a derivative $$$gap'(t)$$$. Finally notice that calculating a derivative $$$gap'(t)$$$ may be done by finding a maximum flow and adding up all slopes of capacities of the edges defining a minimum cut restricting given maximum flow (since exactly this cut provides a linear constraint defining a segment of a function $$$gap(t)$$$, which a point $$$t$$$ belongs to).
An alternative observation — consider only the points $$$t$$$ such that $$$t = \frac{k}{10^7}$$$ where $$$k$$$ is integer. If we keep only such points on the sought segment, its length will decrease by no more than $$$2 \cdot 10^{-7}$$$ which is allowed by a required answer precision. Finally, we can multiply all $$$b_e$$$ and $$$d_e$$$ by $$$10^7$$$ and consider $$$t$$$ to be an integer between $$$0$$$ and $$$10^7$$$ which allows you to implement a solution that only uses integer data types.
We get a solution with a running time of $$$O(maxflow \cdot \log prec^{-1})$$$ where $$$prec$$$ is a required precision equal to $$$10^{-6}$$$ under conditions of a given problem and $$$maxflow$$$ is a running time of your favourite maximum flow algorithm. Practically you could use Dinic algorithm or Edmonds-Karp algorithm with capacity scaling.