Codeforces Global Round 25 |
---|
Закончено |
Вам дан неориентированный связный простой граф с $$$n$$$ вершинами и $$$m$$$ ребрами, где ребро $$$i$$$ соединяет вершины $$$u_i$$$ и $$$v_i$$$. С каждым ребром связаны два положительных параметра $$$a_i$$$ и $$$b_i$$$. Кроме того, вам дано целое число $$$k$$$.
Неотрицательный массив $$$x$$$ длины $$$m$$$ называется генератором $$$k$$$-остовного-дерева, если он удовлетворяет следующим условиям:
Стоимость такого массива $$$x$$$ определяется как $$$\sum_{i = 1}^m a_i x_i^2 + b_i x_i$$$. Найдите минимальную стоимость генератора $$$k$$$-остовного-дерева.
$$$^\dagger$$$ Остовное дерево (мульти)графа — это подмножество ребер графа, которые образуют дерево, соединяющее все вершины графа.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$2 \le n \le 50, n - 1 \le m \le \min(50, \frac{n(n - 1)}{2}), 1 \le k \le 10^7$$$) — количество вершин в графе, количество ребер в графе и параметр для генератора $$$k$$$-остовного-дерева.
Каждая из следующих $$$m$$$ строк каждого набора входных данных содержит четыре целых числа $$$u_i$$$, $$$v_i$$$, $$$a_i$$$ и $$$b_i$$$ ($$$1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le a_i, b_i \le 1000$$$) — конечные точки ребра $$$i$$$ и два его параметра. Гарантируется, что граф прост и связен.
Гарантируется, что сумма $$$n^2$$$ и сумма $$$m^2$$$ по всем наборам входных данных не превосходит $$$2500$$$.
Для каждого набора входных данных выведите одно целое число: минимальную стоимость генератора $$$k$$$-остовного-дерева.
45 5 14 3 5 52 1 5 72 4 6 25 3 3 52 5 2 95 5 34 3 5 52 1 5 72 4 6 25 3 3 52 5 2 92 1 100000001 2 1000 100010 15 107 1 7 65 8 6 64 8 2 24 3 10 910 8 3 44 6 6 15 4 1 39 3 4 38 3 9 97 5 10 32 1 3 46 1 6 42 5 7 310 7 2 18 2 6 8
38 191 100000010000000000 2722
В первом наборе входных данных допустимым генератором $$$1$$$-остовного-дерева является $$$x = [1, 1, 1, 1, 0]$$$, как показано на следующем рисунке. Стоимость этого генератора равна $$$(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$$$. Можно доказать, что ни один другой генератор не имеет меньшей стоимости.
Во втором наборе входных данных допустимым генератором $$$3$$$-остовного-дерева является $$$x = [2, 3, 2, 2, 3]$$$, как показано на следующем рисунке. Стоимость этого генератора равна $$$(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$$$. Можно доказать, что ни один другой генератор не имеет меньшей стоимости.
Название |
---|