← 返回题目列表

Codeforces · 1970/G2

G2. Min-Fund 监狱(中型)

中文机器翻译题面 查看原题

在中等版本中,$$$2 \leq \sum n \leq 300$$$ 和 $$$1 \leq \sum m \leq 300$$$

在摄魂怪组织的工人罢工要求平等权利之后,阿兹卡班监狱受到了一些破坏。安定了灵魂之后,魔法部正在考虑翻新监狱,以确保摄魂怪受到控制。监狱由$$$n$$$牢房和$$$m$$$双向走廊组成。 $$$i^{th}$$$ 走廊是从单元格 $$$u_i$$$ 到 $$$v_i$$$。如果 $$$S$$$ 中的任何单元可从 $$$S$$$ 中的任何其他单元到达,则这些单元 $$$S$$$ 的子集称为复合体。形式上,如果 $$$x$$$ 和 $$$y$$$ 对于 S$$$ 中的所有 $$$x, y 彼此可达,且仅使用来自 $$$S$$$ 的单元格,则单元格 $$$S$$$ 的子集是复数。由 $$$k$$$ 单元组成的复杂 $$$S$$$ 所需的资金定义为 $$$k^2$$$。

作为霍格沃茨魔法室内设计入门课程的一部分,你的任务是设计监狱。魔法部要求你将监狱分成 $$$2$$$ 建筑群,并用 $$$\textbf{恰好一条走廊}$$$ 连接它们,这样摄魂怪就无法组织工会会议。为此,您可以建造双向走廊。在任何 $$$2$$$ 单元之间建造走廊所需的资金为 $$$c$$$。

由于预算削减和与食死徒的持续斗争,您必须找到按照部委要求分割监狱所需的 $$$\textbf{最低总资金}$$$ 或 $$$-1$$$(如果无法分割)。

注:总资金是$$$2$$$综合体和走廊所需资金的总和。如果分割后,两个综合体分别有 $$$x$$$ 和 $$$y$$$ 单元,并且您总共建造了 $$$a$$$ 走廊,则总资金将为 $$$x^2 + y^2 + c \times a$$$。请注意 $$$x+y=n$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 300$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例的第一行由三个整数 $$$n、m$$$ 和 $$$c$$$ 组成($$$2 \leq n \leq 300$$$、$$$1 \leq m \leq 300$$$、$$$1 \leq c \leq 10^9$$$)

$$$m$$$ 行,每行由 2 个整数组成 — $$$u_i, v_i$$$ 表示单元格 $$$u_i$$$ 和 $$$v_i$$$ 之间存在走廊 ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$)

保证所有测试用例的 $$$n$$$ 总和不超过 $$$300$$$。

保证所有测试用例的 $$$m$$$ 总和不超过 $$$300$$$。

保证任意两个单元之间最多存在一条走廊。

输出

打印按照部委要求分割监狱所需的 $$$\textbf{最低资金}$$$ 或 $$$-1$$$(如果无法分割)。

示例

输入 #1

4
4 6 5
4 3
2 3
2 4
1 2
4 1
3 1
6 6 2
1 4
2 5
3 6
1 5
3 5
6 5
6 5 7
1 4
2 5
3 6
3 5
6 5
7 5 4
1 4
3 6
3 5
6 5
2 7

输出 #1

-1
20
25
33

注意

在样本输入的第一个测试案例中,没有办法按照部委的要求划分监狱。

在第二个测试用例中,将单元格 $$$1$$$ 和 $$$5$$$ 之间的走廊视为分别由 $$$\{2, 3, 5, 6\}$$$ 和 $$$\{1, 4\}$$$ 单元格组成的 $$$2$$$ 复合体之间的连接。没有修建新​​的走廊。总资金为 $$$4^2 + 2^2 = 20$$$。您可以验证这是所需的最低资金。

在第三个测试用例中,在 $$$2$$$ 和 $$$4$$$ 之间构建一条走廊。将单元格 $$$1$$$ 和 $$$5$$$ 之间的走廊视为分别由 $$$\{3, 5, 6\}$$$ 和 $$$\{1, 2, 4\}$$$ 单元格组成的 $$$2$$$ 复合体之间的连接。总资金为 $$$3^2 + 3^2 + 7 \times 1 = 25$$$。您可以验证这是所需的最低资金。

在第四个测试用例中,在 $$$2$$$ 和 $$$4$$$ 之间以及 $$$5$$$ 和 $$$7$$$ 之间构建一条走廊。将单元格 $$$5$$$ 和 $$$7$$$ 之间的走廊视为分别由 $$$\{1, 2, 4, 7\}$$$ 和 $$$\{3, 5, 6\}$$$ 单元格组成的 $$$2$$$ 复合体之间的连接。总资金为 $$$4^2 + 3^2 + 4 \times 2 = 33$$$。您可以验证这是所需的最低资金。

请注意,所有测试用例可能有多种方式获得相同的资金,但没有其他部门具有更优化的最低资金。