311223: CF1951I. Growing Trees
Description
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.
InputEach 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$.
OutputFor each test case, output a single integer: the minimum cost of a $k$-spanning-tree generator.
ExampleInput4 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 8Output
38 191 100000010000000000 2722Note
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.
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.
Output
输入输出数据格式:
输入:
- 第一行包含一个整数t(1≤t≤500),表示测试用例的数量。
- 每个测试用例的第一行包含三个整数n、m和k(2≤n≤50, n-1≤m≤min(50, n(n-1)/2), 1≤k≤10^7),分别表示图中的节点数、边数和k-生成树生成器的参数。
- 接下来的m行,每行包含四个整数\(u_i\)、\(v_i\)、\(a_i\)和\(b_i\)(1≤\(u_i\), \(v_i\)≤n, \(u_i\)≠\(v_i\), 1≤\(a_i\), \(b_i\)≤1000),分别表示边i的两个端点和其两个参数。保证图是简单且连通的。
- 保证所有测试用例的\(n^2\)和\(m^2\)之和不超过2500。
输出:
- 对于每个测试用例,输出一个整数:k-生成树生成器的最小成本。题目大意:给定一个无向连通简单图,有n个节点和m条边,每条边连接两个节点,并附有两个正参数a_i和b_i。另外,还给出了一个整数k。需要找到一个非负数组x(大小为m),称为k-生成树生成器,其满足以下条件:考虑一个无向多重图,在该图中边i被克隆x_i次,可以将其边划分为k棵生成树,每条边恰好属于一棵生成树。数组x的成本定义为 \(\sum_{i = 1}^m a_i x_i^2 + b_i x_i\)。需要找到成本最小的k-生成树生成器。 输入输出数据格式: 输入: - 第一行包含一个整数t(1≤t≤500),表示测试用例的数量。 - 每个测试用例的第一行包含三个整数n、m和k(2≤n≤50, n-1≤m≤min(50, n(n-1)/2), 1≤k≤10^7),分别表示图中的节点数、边数和k-生成树生成器的参数。 - 接下来的m行,每行包含四个整数\(u_i\)、\(v_i\)、\(a_i\)和\(b_i\)(1≤\(u_i\), \(v_i\)≤n, \(u_i\)≠\(v_i\), 1≤\(a_i\), \(b_i\)≤1000),分别表示边i的两个端点和其两个参数。保证图是简单且连通的。 - 保证所有测试用例的\(n^2\)和\(m^2\)之和不超过2500。 输出: - 对于每个测试用例,输出一个整数:k-生成树生成器的最小成本。