← 返回题目列表

Codeforces · 1556/H

H. DIY 树

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

William 非常喜欢拼图套件。在他的一个生日那天,他的朋友送给他一张完整的无向边加权图,由 $$$n$$$ 个顶点组成。

他想要构建该图的生成树,使得对于前$$$k$$$个顶点满足以下条件:索引为$$$i$$$的顶点的度不超过$$$d_i$$$。从 $$$k + 1$$$ 到 $$$n$$$ 的顶点可以有任意度数。

William 希望你找到满足所有条件的生成树的最小权值。

生成树是图的边的子集,它在图的所有 $$$n$$$ 顶点上形成一棵树。生成树的权重定义为生成树中包含的所有边的权重之和。

输入

输入的第一行包含两个整数 $$$n$$$, $$$k$$$ ($$$2 \leq n \leq 50$$$, $$$1 \leq k \leq min(n - 1, 5)$$$)。

第二行包含 $$$k$$$ 整数 $$$d_1, d_2, \ldots, d_k$$$ ($$$1 \leq d_i \leq n$$$)。

接下来的 $$$n - 1$$$ 行中的第 $$$i$$$ 包含 $$$n - i$$$ 整数 $$$w_{i,i+1}, w_{i,i+2}, \ldots, w_{i,n}$$$ ($$$1 \leq w_{i,j} \leq 100$$$):边的权重$$$(i,i+1),(i,i+2),\ldots,(i,n)$$$。

输出

打印一个整数:在给定度数约束下第一个 $$$k$$$ 顶点的生成树的最小权重。

示例

输入 #1

10 5
5 3 4 2 1
29 49 33 12 55 15 32 62 37
61 26 15 58 15 22 8 58
37 16 9 39 20 14 58
10 15 40 3 19 55
53 13 37 44 52
23 59 58 4
69 80 29
89 28
48

输出 #1

95