← 返回题目列表

AtCoder · waipc_qual_b

B. 准备获胜的游戏

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

配点 : 700 点

問題文

1 减去 N 编号最多为 N 由顶点组成的加权完全无向图 G 。 顶点 i 和边 j (1 \leq i < j \leq N) 所连接的边的权重为 C_{i,j} 。 求放置超过

Alice 和 Bob 将进行这场游戏。首先作为游戏准备,Bob 将进行以下操作。

  • G 减去 0 删除以上的边。这里将删除的边的权重总和写在成本 需要。
  • 顶点中任意选择的 A 个上,并写入 A 。剩下的 N-A 个写入 B 。
  • 任意选择的顶点 1 个,在上面放置 1 个棋子。

准备完成后开始游戏。由 Alice 开始,两名玩家轮流进行操作。 每回合可以进行以下任意动作:

  • 结束游戏。
  • 将棋子移动到相邻的顶点。但不能移动到曾经放置过棋子的顶点(包括游戏开始时已有棋子的顶点)。

游戏结束瞬间棋子所在顶点写着的文字为 A 的话,Alice 获胜,B 的话,Bob 获胜。 Bob 想要准备游戏,使自己存在必胜法。 请找出为此所需的最小成本。 请解决

1 每个输入,T 个案例。 跨越

制約

  • 1 \leq T \leq 100
  • 2 \leq N \leq 20
  • 1 \leq A \leq N-1
  • 0 \leq C_{i,j} \leq 10^9
  • T 个案例 N^2 的总和是 20^2 以下
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

T
case_1
case_2
\vdots
case_T

每个测试用例的格式如下。

N A
C_{1,2} C_{1,3} \ldots C_{1,N}
C_{2,3} \ldots C_{2,N}
\vdots
C_{N-1,N}

出力

对每个测试用例输出答案。


入力例 1

4
2 1
1
4 2
0 1 0
1 1
1
4 3
0 1 0
1 1
1
10 6
920863892 404674703 404674703 972355497 19199103 13614516 2354795 994561596 404674703
333091354 956864449 832425833 949490369 267560921 607314403 595085993 147983762
979679626 425301247 13605197 11023257 25122957 333091354 925837072
629748489 333702011 455328188 529811895 662742653 679478024
532156763 300916094 645258473 298300578 337246479
523721752 333702011 1356103 9719790
657515163 3035530 3007974
15464189 19594391
298300578

出力例 1

1
0
1
137097802

1 对于第几号测试用例,可以按如下方式准备游戏。

  • 辺 (1,2) 删除。成本是 1 需要。
  • 頂点 1,2 分别 添加 A,B 。
  • 将棋子放在顶点 2 。

2 对于第几号测试用例,可以按如下方式准备游戏。

  • 辺 (1,2),(1,4) 删除。成本是 0 需要。
  • 頂点 1,2,3,4 分别 添加 B,A,B,A 。
  • 将棋子放在顶点 1 。