Growing Trees
Contest: Codeforces Global Round 25
Difficulty rating: 3200
Tags: binary search, constructive algorithms, flows, graphs, greedy

You are given an undirected connected simple graph with $$$n$$$ nodes and $$$m$$$ edges, where edge $$$i$$$ connects node $$$u_i$$$ and $$$v_i$$$, with two positive parameters $$$a_i$$$ and $$$b_i$$$ attached to it. Additionally, you are also given an integer $$$k$$$.

A non-negative array $$$x$$$ with size $$$m$$$ is called a $$$k$$$-spanning-tree generator if it satisfies the following:

- Consider the undirected multigraph with $$$n$$$ nodes where edge $$$i$$$ is cloned $$$x_i$$$ times (i.e. there are $$$x_i$$$ edges connecting $$$u_i$$$ and $$$v_i$$$). It is possible to partition the edges of this graph into $$$k$$$ spanning trees, where each edge belongs to exactly one spanning tree$$$^\dagger$$$.

The cost of such array $$$x$$$ is defined as $$$\sum_{i = 1}^m a_i x_i^2 + b_i x_i$$$. Find the minimum cost of a $$$k$$$-spanning-tree generator.

$$$^\dagger$$$ A spanning tree of a (multi)graph is a subset of the graph's edges that form a tree connecting all vertices of the graph.

Input format:
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 500$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$2 \le n \le 50, n - 1 \le m \le \min(50, \frac{n(n - 1)}{2}), 1 \le k \le 10^7$$$) — the number of nodes in the graph, the number of edges in the graph, and the parameter for the $$$k$$$-spanning-tree generator.

Each of the next $$$m$$$ lines of each test case contains four integers $$$u_i$$$, $$$v_i$$$, $$$a_i$$$, and $$$b_i$$$ ($$$1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le a_i, b_i \le 1000$$$) — the endpoints of the edge $$$i$$$ and its two parameters. It is guaranteed that the graph is simple and connected.

It is guaranteed that the sum of $$$n^2$$$ and the sum of $$$m^2$$$ over all test cases does not exceed $$$2500$$$.

Output format:
For each test case, output a single integer: the minimum cost of a $$$k$$$-spanning-tree generator.

Constraints:
Time limit: 5.0 s
Memory limit: 512.0 MB

Note:
In the first test case, a valid $$$1$$$-spanning-tree generator is $$$x = [1, 1, 1, 1, 0]$$$, as indicated by the following figure. The cost of this generator is $$$(1^2 \cdot 5 + 1 \cdot 5) + (1^2 \cdot 5 + 1 \cdot 7) + (1^2 \cdot 6 + 1 \cdot 2) + (1^2 \cdot 3 + 1 \cdot 5) + (0^2 \cdot 4 + 0 \cdot 9) = 38$$$. It can be proven that no other generator has a lower cost.

The $$$1$$$-spanning-tree partition of $$$x = [1, 1, 1, 1, 0]$$$

In the second test case, a valid $$$3$$$-spanning-tree generator is $$$x = [2, 3, 2, 2, 3]$$$, as indicated by the following figure. The cost of this generator is $$$(2^2 \cdot 5 + 2 \cdot 5) + (3^2 \cdot 5 + 3 \cdot 7) + (2^2 \cdot 6 + 2 \cdot 2) + (2^2 \cdot 3 + 2 \cdot 5) + (3^2 \cdot 4 + 3 \cdot 9) = 191$$$. It can be proven that no other generator has a lower cost.

The $$$3$$$-spanning-tree partition of $$$x = [2, 3, 2, 2, 3]$$$

Example input:
4
5 5 1
4 3 5 5
2 1 5 7
2 4 6 2
5 3 3 5
2 5 2 9
5 5 3
4 3 5 5
2 1 5 7
2 4 6 2
5 3 3 5
2 5 2 9
2 1 10000000
1 2 1000 1000
10 15 10
7 1 7 6
5 8 6 6
4 8 2 2
4 3 10 9
10 8 3 4
4 6 6 1
5 4 1 3
9 3 4 3
8 3 9 9
7 5 10 3
2 1 3 4
6 1 6 4
2 5 7 3
10 7 2 1
8 2 6 8

Example output:
38
191
100000010000000000
2722

Editorial:
From now on, we say an array $$$x$$$ to be good if the graph created by cloning the $$$i$$$-th edge $$$x_i$$$ times can be partitioned into $$$k$$$ forests (this is slightly different from $$$k$$$-spanning-tree generators).
Let's first discuss how to check whether an array $$$x$$$ is good. Let $$$G'$$$ be the graph created by cloning the $$$i$$$-th edge $$$x_i$$$ times. By Nash-Williams theorem, for every subset of vertices $$$U$$$, we need the induced subgraph $$$G'[U]$$$ to have at most $$$k(|U| - 1)$$$ edges, so it suffices to check this condition quickly. Furthermore, this condition can easily be modified to $$$k$$$-spanning-tree generators: the only additional condition necessary is to have $$$\sum_{i=1}^m x_i = k(n - 1)$$$.
Consider the unweighted bipartite graph $$$B_{G'}$$$ where every left node represents a node $$$u$$$ of $$$G'$$$, every right node represents an edge $$$(u, v)$$$ of $$$G'$$$, and we connect edges $$$u - (u, v)$$$ and $$$v - (u, v)$$$ for every right node $$$(u, v)$$$, then Hall's marriage theorem states that $$$B_{G'}$$$ has a right-saturating matching iff the induced subgraph $$$G'[U]$$$ has at most $$$|U|$$$ edges for all $$$U$$$. We can further extend this idea by making $$$k$$$ clones of every left node $$$u$$$, which now means that the $$$B_{G'}$$$ has a right-saturating matching iff $$$|G'[U]| \le k |U|$$$ for all $$$U$$$. The big last idea is to try "turning off" a left node $$$u$$$: formally, consider $$$B_{G', u}$$$ be the same as $$$B_{G'}$$$, but all clones of some left node $$$u$$$ are deleted, and note that this graph enforces the condition $$$|G'[U']| \le k(|U'| - 1)$$$ for every subset $$$U'$$$ containing $$$u$$$. Therefore, by checking if $$$B_{G', u}$$$ has a right-saturating matching matching for all $$$u$$$, we can now ensure the Nash-Williams condition. Finally, note that we can quickly check if $$$B_{G', u}$$$ has a right-saturating matching by constructing the following directed graph: direct an edge from the source node to every left node $$$v \neq u$$$ with capacity $$$k$$$, direct an edge from every right node $$$(u_i, v_i)$$$ to the sink node with capacity $$$x_i$$$, and direct an edge from left node $$$u_i$$$ (or $$$v_i$$$) to right node $$$(u_i, v_i)$$$ with capacity $$$\infty$$$; $$$B_{G', u}$$$ has a perfect matching iff this new graph has a flow from source to sink that saturates all incoming edges to sink. As the constructed flow graph has $$$O(n + m)$$$ nodes and edges, we now know how to check if an array $$$x$$$ is good in time complexity $$$O(n \cdot F(n + m, n + m))$$$, where $$$F(N, M)$$$ is the complexity to run max flow on a graph with $$$N$$$ nodes and $$$M$$$ edges.
We now return to the original problem. Observe that the cost function is convex on every coordinate $$$x_i$$$; hence, one could imagine the following greedy strategy: starts with $$$x = 0$$$; until the sum of $$$x_i$$$ reaches $$$k(n - 1)$$$, try to find a coordinate $$$i$$$ and increases $$$x_i$$$ by $$$1$$$ such that
• increasing $$$x_i$$$ by $$$1$$$ doesn't make $$$x$$$ bad, and
• increasing $$$x_i$$$ by $$$1$$$ increases the cost by as little as possible.
It turns out that this strategy works, as the set of all good arrays forms a "matroid", and $$$k$$$-spanning-tree generators are the "bases" of this "matroid" (note that the greedy algorithm guarantees to find the min-weight basis of a matroid). To be more formal, consider a set of elements $$$E$$$, where each element denoted by a pair $$$(i, t)$$$ represents the clone of the edge $$$i$$$ with cost $$$(a_i t^2 + b_i t) - (a_i (t-1)^2 + b_i(t - 1))$$$, and a subset $$$E' \subseteq E$$$ is independent if the multiset edges represented by elements in $$$E'$$$ can be partitioned into $$$k$$$ forests (here, we let $$$i \in [1, n]$$$ and $$$t \in [1, k]$$$). Observe that this set $$$E$$$ forms a matroid (we can think of $$$E$$$ as a "permuted" direct sum of $$$k$$$ disjoint versions of the graphic matroids on $$$G$$$, and note that direct sums of matroids are themselves matroid). Furthermore, the weight of element $$$(i, t)$$$ represents exactly the increment to the cost when we increase $$$x_i$$$ from $$$t - 1$$$ to $$$t$$$. By convexity of the cost on each edge, the weight of $$$(i, t)$$$ is less than the weight of $$$(i, t + 1)$$$. Hence the min-cost $$$k$$$-spanning-tree generator represents exactly the min-weight basis of $$$E$$$, as the basis would greedily use $$$(i, j)$$$ with $$$j$$$ being as small as possible.
Finally, while this greedy algorithm is correct, we still need to optimize it as the number of steps is $$$k(n - 1)$$$. Observe that if at some step, increasing a coordinate $$$i$$$ makes $$$x$$$ bad, we would never consider coordinate $$$i$$$ again at later steps of the algorithm. Therefore, we can effectively simulate the greedy algorithm by 1) finding the first step where a coordinate $$$i$$$ turns bad, 2) advancing until such step, 3) discarding coordinate $$$i$$$ from consideration, and 4) repeating until every coordinate turns bad. Fortunately, step 1) can be quickly implemented by binary searching on the cost of the increment, and the number of iterations is $$$m$$$ as every coordinate can only be discarded once. Therefore, the problem has been solved in time complexity of either $$$O(m \cdot (\log W + m) \cdot n \cdot F(n + m, n + m))$$$, $$$O(m \cdot \log mW \cdot n \cdot F(n + m, n + m))$$$, or $$$O(m \cdot \log W \cdot n \cdot F(n + m, n + m) + m^2 n^2)$$$ depending on how you break ties on the same cost increment (note that we can ensure no ties by adding $$$\epsilon i$$$ to $$$x_i$$$), where $$$W \le 2 k \cdot \max a + \max b$$$ is the maximum cost increment.