Standard definition of LP dual problem looks like this:

Considering some more generic forms, it may be summarized in a table:

Or, keeping it more visual, we may write it as follows:

Statement as it is boils down to the following LP problem, given $$$a_1, \dots, a_n, b_1, \dots, b_n, p, q$$$:

Its dual is

The optimal solution to the dual problem can be found in $$$O(\log C)$$$ with ternary search.

Minimum cost $$$b$$$-flow is formulated as LP problem in the following way:

Note that Library Checker's formulation is a bit more generic and also uses lower constraints $$$l_{ij} \leq f_{ij}$$$ instead of just $$$0 \leq f_{ij}$$$, besides $$$b_1, \dots, b_n$$$ in Library Checker's formulation are given in input, rather than fixed with source $$$s$$$ and sink $$$t$$$. Worst of all, it seemingly allows negative cost cycles, thus one would need to utilize some algorithm that finds a minimum cost circulation after finding some $$$b$$$-flow.

We will only consider simplified version above to share the core idea.

In terms of the primary problem, the dual variables are defined by the complementary slackness:

1. If $$$f_{ij} > 0$$$, then $$$c_{ij}^\pi \leq 0$$$;
2. If $$$f_{ij} < q_{ij}$$$, then $$$c_{ij}^\pi \geq 0$$$.

Here $$$c_{ij}^\pi = c_{ij} + \pi_j - \pi_i$$$ is the adjusted cost of the edge $$$i \to j$$$.

For further detailed explanation, please refer to the minimum cost flow part of my previous article.

The dual of minimum cost $$$b$$$-flow problem may be formulated directly as

One of possible way to find $$$\pi_k$$$ knowing the residual network of a minimum cost $$$b$$$-flow is to assign $$$\pi_k$$$ the negated shortest path length from $$$s$$$ to $$$k$$$ in the residual network. Alternatively, $$$\pi_k$$$ may be perceived as the shortest path from $$$k$$$ to $$$t$$$. Knowing residual network of a minimum cost $$$b$$$-flow, it's possible to compute potentials in $$$O(nm)$$$ with any shortest path algorithm that allows negative edges.

Again, for further detailed explanation, please refer to the minimum cost flow part of my previous article.

Generally, it is a known property that a spanning tree is minimum if and only if the cost of any external edge $$$j$$$ is not smaller than any cost of an edge on the tree path $$$p_j$$$ that connects the endpoints of $$$j$$$. In other words, $$$d_i \leq d_j (\forall i \in p_j)$$$.

The statement above, using $$$d_i = c_i - x_i$$$ for $$$i \in T$$$ and $$$d_j = c_j + x_j$$$ for $$$j \not \in T$$$, is formulated as an LP problem in the following way:

Solving the original problem is not a trivial task, however we might formulate its dual:

It's not hard to see that the dual is, in fact, an assignment problem on bipartite graph.

Edges $$$i \in T$$$ form one part of the graph, while edges $$$j \not\in T$$$ form another part of the graph, and the edge between $$$i$$$ and $$$j$$$ costs $$$c_{i} - c_j$$$ and has the capacity $$$1$$$. This already allows us to recover the minimum sum $$$x_1 + \dots + x_m$$$, but the problem asks us to find optimal $$$d_1, \dots, d_m$$$, that is to also find the actual values of $$$x_1,\dots, x_m$$$.

For convenience, let's change edge weights from $$$c_i - c_j$$$ to $$$c_j - c_i$$$ and work with minimum cost flow instead, as we're more familiar with its potentials and their properties than with maximum cost flow.

Let's see how minimum cost flow potentials relate with this problem. Adjusted weights of edges in minimum cost flow are defined as $$$c_{ij}^\pi = c_{ij} + \pi_j - \pi_i$$$. And we know that $$$c_{ij}^\pi \geq 0$$$ for non-saturated edges, while $$$c_{ij}^\pi \leq 0$$$ for edges with non-zero flow. What does it mean for edges in the residual network? The edge $$$i \to j$$$ of cost $$$c_j - c_i$$$ would change to

Then, making edge $$$i \to j$$$ of infinite capacity, we will guarantee that $$$c_{ij}^\pi = 0$$$ for edges that participate in the assignment and $$$c_{ij}^\pi \geq 0$$$ for all other edges, hence $$$c_j + \pi_j \geq c_i + \pi_i$$$ for any edge in the bipartite graph. This means that

would define feasible values of $$$x_1, \dots, x_m$$$. Not necessarily optimal however. What is the total cost of the assignment defined by the residual network with potentials $$$\pi_1, \dots, \pi_m$$$? Any edge participating in the assignment would have zero cost and won't contribute to the assignment value. This only leaves us with edges $$$s \to i$$$, having costs $$$\pi_i-\pi_s$$$ and edges $$$j \to t$$$, having cost $$$\pi_t-\pi_j$$$. Here, $$$\pi_t$$$ and $$$\pi_s$$$ summed up together give an extra factor of $$$b(\pi_t - \pi_s)$$$ in the minimum cost dual.

In this factor we should note that $$$\pi_s=0$$$ by definition when using shortest path from $$$s$$$ potentials, and $$$\pi_t \geq 0$$$ in the moment at which we're no longer able to use augmenting paths of negative cost. To not consider $$$\pi_t > 0$$$ case separately it is convenient to adjust the flow network by adding a direct edge $$$s \to t$$$ of cost $$$0$$$ and positive capacity. This way we guarantee that when all negative-cost paths are exhausted, we will have $$$\pi_t=0$$$ and thus we may ignore it.

The property above means that the optimal cost is obtained if we only use potentials of the vertices that actually participate in the assignment. It hints that we may just change potentials of all the other vertices to $$$0$$$ and it would still be a feasible solution.

Why is it true? Consider a vertex $$$i$$$ in the first part of the bipartite graph that wasn't taken in the assignment. Its potential (negated shortest path from $$$s$$$) must be non-negative, as there is still an edge $$$s \to i$$$ of the cost $$$0$$$. Consider a vertex $$$j$$$ in the second part that wasn't taken in the assignment. Its potential must be non-positive, as there is still an edge $$$j \to t$$$.

If we'd use such potentials in $$$x_i$$$ and $$$x_j$$$ we would increase the cost of edges in $$$T$$$ and decrease the cost of edges not in $$$T$$$. We get a feasible solution after doing it, but it means that we were fine before doing it to begin with, so changing the potentials to $$$0$$$ is OK.

Summarizing everything above, the algorithm is as follows:

1. Construct the flow network for the assignment problem;
2. Add an extra edge $$$s \to t$$$ with cost $$$0$$$ and positive capacity;
3. Find minimum-cost flow $$$f$$$;
4. Find the potentials, $$$\pi_k$$$ for vertex $$$k$$$ is the negated length of a shortest path from $$$s$$$ to $$$k$$$ in the residual network;
5. For every $$$k$$$ that participates in the resulting assignment (is incident to saturated edge), add $$$\pi_k$$$ to $$$c_k$$$ to get $$$d_k$$$.

Possible implementation.

The problem is quite similar to 605C that is explained above. It's LP formulation is as follows:

For each of $$$n$$$ constraints, we'll have a dual variable $$$\pi_k$$$ and each of $$$2n-2$$$ primal variables will generate a constraint.

To get the coefficient near $$$i$$$-th dual variable in the $$$j$$$-th constraint, we take the coefficient near $$$j$$$-th primal variable in the $$$i$$$-th primal constraint. E.g. the variable $$$p_k$$$ occurs in the $$$k$$$-th constraint with the coefficient $$$x$$$ and in the $$$(k+1)$$$-th constraint with the coefficient $$$y$$$:

Consider the case of only two variables:

The constraints define a quadrilateral with four vertices:

The quadrilateral defined by the inequalities and its vertices

Thus the space of allowed $$$\pi_1, \dots, \pi_n$$$ may be interpreted in the following way: There is a convex quadrilateral defined by the inequalities and $$$(n-1)$$$ points, $$$k$$$-th point having coordinate $$$(\pi_k, \pi_{k+1})$$$. You may arbitrary number of times add same value to the $$$x$$$ coordinate of the $$$k$$$-th point and $$$y$$$ coordinate of the $$$(k-1)$$$-th point, while making sure that all points stay within the quadrilateral.

Besides that, you may freely change the $$$x$$$ coordinate of the first point and the $$$y$$$ coordinate of the last point, obviously always making them as large as possible, as $$$a_1,\dots, a_n \geq 0$$$.

Next step in the solution is to notice that it's always possible to pick a solution of LP which is a vertex of the polytope defined by the constraints (as long as the polytope is bounded). That is, it's always possible to pick a subset of $$$n$$$ inequalities that will be "saturated". In this particular problem, however, all inequalities concern either only $$$1$$$ or only $$$2$$$ variables, so we may construct a graph in which there is an edge between $$$i$$$ and $$$j$$$ whenever there is an inequality that concerns both $$$\pi_i$$$ and $$$\pi_j$$$.

In such graph, an edge $$$(u, v)$$$ would mean that we're able to recover $$$u$$$ if we know $$$v$$$ and vice versa. Besides that, it is also possible to resolve any cycle, as substituting variables along the cycle allows us to return to the first variable of the cycle with the equation of form $$$ax=b$$$. For the set of $$$n$$$ equations to have a unique solution it is sufficient that each connected component has a cycle. Moreover, since we only use $$$n$$$ edges for $$$n$$$ vertices, the cycle of each component must be unique.

Another particularity of this specific problem is that all cycles, if they're unique in their connected component, will be either self-loops (if we take the equation $$$\pi_k = 0$$$) or between only two vertices (if we take both equations $$$x\pi_k + y \pi_{k+1} = 1$$$ and $$$x \pi_{k+1} + y \pi_k = 1$$$).

In the first case, vertices with even distance from the root will hold $$$0$$$.

And the vertices with odd distance from the root will hold $$$\frac{1}{\max(x, y)}$$$, because $$$\frac{1}{\min(x, y)}$$$ would violate the constraints.

In the second case, all vertices in the connected component will hold the value of $$$\frac{1}{x+y}$$$.

Primal problem is formulated in a straightforward manner. Let $$$x_{ij}$$$ be the amount of snack of type $$$j$$$ distributed to $$$i$$$-th child:

It can as well be perceived as a maximum flow problem, such that from the source $$$s$$$ to $$$j$$$-th snack there is an edge of capacity $$$A_j$$$, from $$$j$$$-th snack to $$$i$$$-th child there is an edge of capacity $$$B_i$$$ and from $$$i$$$-th child to the sink $$$t$$$ there is an edge of capacity $$$C_i$$$.

The network is too huge for computing maximum flow on it, so let's write the dual problem. There will be $$$n+m+nm$$$ dual variables, let $$$\lambda_j$$$ be a variable for the $$$\leq A_j$$$ constraint, $$$\mu_i$$$ be a variable for the $$$\leq C_i$$$ constraint and $$$\nu_{ij}$$$ be a variable for the $$$\leq B_i$$$ constraint.

Then, the dual problem is written as

Since the primal problem is a maximum flow in the bipartite graph, its dual may be interpreted as minimum cut in the graph. To be more specific, each of the variables $$$\lambda_j$$$, $$$\mu_i$$$ and $$$\nu_{ij}$$$ will be either $$$0$$$ or $$$1$$$, depending on whether corresponding edges are taken into the cut.

It means that for each pair $$$(j, i)$$$, we either we delete the $$$j$$$-th vertex in the first part ($$$\lambda_j = 1$$$) and pay $$$A_j$$$, or delete the $$$i$$$-th vertex in the second part ($$$\mu_i = 1$$$) and pay $$$C_i$$$ or delete the edge from $$$j$$$-th vertex in the first part to the $$$i$$$-th vertex in the second part and pay $$$B_i$$$.

Let $$$X_0$$$ and $$$Y_0$$$ be the sets of removed vertices in the first and the second parts correspondingly, and let $$$X_1$$$ and $$$Y_1$$$ be the sets of non-removed vertices in the parts. Then the value of the target function is expressed as

Using the fact that the third sum does not depend on $$$A_1$$$, but only on its size, we further rewrite it as

Let $$$f(k)$$$ be the minimum value of the target function with $$$|X_1| = k$$$, then

For each specific $$$k$$$, it is always optimal to pick $$$X_0$$$ as a prefix of all snacks, sorted in increasing order of $$$A_j$$$. At the same time, for each $$$i$$$ we know the minimum $$$k$$$ starting from which it is better to use $$$C_i$$$ rather than $$$k B_i$$$. Together, it allows to compute $$$f(k)$$$ for any fixed $$$k$$$ in $$$O(\log n)$$$ amortized time by e.g. using prefix sums and binary search. Then, you just pick $$$k$$$ such that $$$f(k)$$$ is minimum possible.

Let $$$\alpha_i$$$ be the number of cameras in $$$i \in L$$$ and $$$\beta_j$$$ be the number of cameras in $$$j \in R$$$. Then the primal LP is as follows:

Dual problem will introduce a dual variable $$$\lambda_{ij}$$$ for each constraint. Then it is formulated as

Formulation is quite similar to ARC 125 Snack. Indeed, it's nothing but the maximum cost flow in the network constructed as follows:

• There is an edge of cost $$$0$$$ and capacity $$$A_i$$$ from $$$s$$$ to every $$$i \in L$$$;
• There is an edge of cost $$$0$$$ and capacity $$$B_j$$$ from every $$$j \in R$$$ to $$$t$$$;
• There is an edge of cost $$$C_{ij}$$$ and capacity $$$+\infty$$$ from $$$A_i$$$ to $$$B_j$$$ for every $$$i \in L$$$ and $$$j \in R$$$.

Note that any tree is a bipartite graph, and maximum-cost $$$k$$$-matching can be formulated as follows:

Let $$$\nu_i$$$ be a dual variable for $$$i \in V$$$ constraint, and $$$\lambda$$$ be a dual variable for $$$=k$$$ constraint. The dual problem is formulated as

Let $$$t(\lambda)$$$ be the minimum with a fixed $$$\lambda$$$. Then the value $$$t(\lambda) - \lambda k$$$ is the solution to the minimization problem

Here $$$C_{ij}^\lambda = C_{ij} - \lambda$$$. If we're able to compute $$$t(\lambda)-\lambda k$$$ for any $$$\lambda$$$, we may note that the function is convex and therefore its minimum can be found by ternary search. But how to compute it for a fixed $$$\lambda$$$?

There are two ways here. First of all, you can take the second dual and obtain

This is essentially the same problem as the initial one, but this time without $$$=k$$$ constraint. It can be solved in $$$O(n)$$$ with DP on tree.

The other option is to solve for $$$t(\lambda) - \lambda k$$$ directly. This option is left to the curious reader as an exercise.

The problem is formulated as follows:

Here we used $$$\geq 1$$$ constraint as this is the minimum possible difference between two integers.

We will have a dual variable $$$\lambda_{ij}$$$ for each edge $$$(i,j) \in E$$$:

Here $$$b_i$$$ is the "balance" of each vertex, defined as

Essentially the dual problem tells us that the $$$i$$$-th vertex should create (if $$$b_i > 0$$$) or absorb (if $$$b_i < 0$$$) the amount of flow that is equal to $$$|b_i|$$$. At the same time each edge has a cost $$$1$$$ and capacity $$$+\infty$$$, and we want to compute a flow of maximum cost.

To reduce flow creation and absorbtion to only two vertices, we will say that when $$$b_i > 0$$$, there is an edge of cost $$$0$$$ and capacity $$$b_i$$$ from $$$s$$$ to $$$i$$$. Otherwise, we make an edge from $$$i$$$ to $$$t$$$ of cost $$$0$$$ and capacity $$$-b_i$$$.

Note that we need to not only find the size of the answer, but also to recover it. As with inverse MST, we will once again use Johnson's potentials and the complementary slackness.

Let $$$c_{ij}^\pi = c_{ij}+\pi_j - \pi_i$$$ be the adjusted cost of the edge. As we remember, for non-saturated edges it holds that $$$c_{ij}^\pi \geq 0$$$ and for edges with non-zero flow it holds that $$$c_{ij}^\pi \leq 0$$$.

At the same time, for the edges of the initial graph that are used in the flow, it is guaranteed that $$$c_{ij}^\pi = 0$$$, as their capacity is infinite, so they can't be saturated. In other words, for any edge $$$i \to j$$$ it holds that $$$c_{ij} + \pi_j - \pi_i = c_{ij}^\pi \leq 0$$$. Using $$$c_{ij}=1$$$ it means that $$$\pi_i - \pi_j \geq 1$$$ for any edge $$$i \to j$$$, which is exactly what the statement asks for.

On the other hand, the total cost of the flow is determined solely by the edges from $$$s$$$ to $$$i$$$, which contribute $$$b_i\pi_i$$$ to the cost of the flow and the edges from $$$j$$$ to $$$t$$$, which contribute $$$b_j(\pi_t-\pi_j)$$$. Summed up altogether this is equal to the sum of $$$w_{ij} (\pi_i - \pi_j)$$$, as the primal problem asks for, plus an excess of $$$b \pi_t$$$. But this excess is exactly the difference between the mincost flow on the initial and adjusted edges, as this difference is generally equal to $$$b(\pi_t - \pi_s)$$$ and $$$\pi_s=0$$$ from they way we compute potentials.

That being said, the solution is $$$a_k = \pi_k$$$, where $$$\pi_k$$$ is the negated length of the shortest path from $$$s$$$ to $$$k$$$ in the residual network of the maximum flow of maximum cost. Possible implementation.