← 返回题目列表

AtCoder · abc395_g

G. 最小斯坦纳树 2

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

分数: 625 点

问题陈述

给你正整数 N, K,以及 N \times N 矩阵 C=(C_{i,j}) (1\leq i,j\leq N)。可以保证 C_{i,i} = 0 和 C_{i,j} = C_{j,i}.

有一个加权完整图 N 顶点标记 1,2,\dots,N。对于每对顶点 i 和 j 与 i\lt j,连接顶点的边的权重 i 和 j is C_{i,j}.

你有 Q 查询。在 i-th 查询,给你一对不同的整数 s_i 和 t_i (两者之间 K+1 和 N,包含),为此您必须解决以下问题。

A 好图 是 已连接 包含所有顶点的图 1,2,\dots,K,s_i,t_i 通过从上图中删除任意数量的边和顶点(可能为零)获得。

的 成本 一个好的图的 是其边的权重之和。

找到一个好图的最小可能成本。

约束

  • 3 \leq N \leq 80
  • 1\leq K\leq \min(N-2,\textcolor{red}{8})
  • 0 \leq C_{i,j} \leq 10^9 \ (1 \leq i,j \leq N, i \ne j)
  • C_{i,j} = C_{j,i} \ (1 \leq i,j \leq N, i \ne j)
  • C_{i,i} = 0 \ (1 \leq i \leq N)
  • 1 \leq Q \leq 5000
  • K+1 \leq s_i, t_i \leq N \ (1 \leq i \leq Q)
  • s_i \ne t_i \ (1 \leq i \leq Q)
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N K
C_{1,1} C_{1,2} \dots C_{1,N}
C_{2,1} C_{2,2} \dots C_{2,N}
\vdots
C_{N,1} C_{N,2} \dots C_{N,N}
Q
s_1 t_1
s_2 t_2
\vdots
s_Q t_Q

输出

打印 Q 行。

的 i- 第行应包含以下问题的答案 i- 第一个查询。


样本输入 1

5 2
0 395 395 1 1
395 0 1 395 1
395 1 0 395 1
1 395 395 0 1
1 1 1 1 0
3
3 4
3 5
4 5

示例输出 1

4
3
3

让“边缘 i-j”表示连接顶点的边 i 和 j.

对于第一个查询,最好保留以下顶点和边,并删除所有其他顶点和边。成本是 4.

  • 顶点 1,2,3,4,5
  • 边缘 1-4,2-3,3-5,4-5

对于第二个查询,最好保留以下顶点和边,并删除所有其他顶点和边。成本是 3.

  • 顶点 1,2,3,5
  • 边缘 1-5,2-3,3-5

示例输入 2

9 5
0 344670307 744280520 967824729 322288793 152036485 628902494 596982638 853214705
344670307 0 249168130 769431650 532405020 981520310 755031424 86416231 284114341
744280520 249168130 0 80707350 256358888 620411718 713892371 272961036 836365490
967824729 769431650 80707350 0 45539861 298766521 722757772 623807668 366719378
322288793 532405020 256358888 45539861 0 361324668 69837030 222135106 935147464
152036485 981520310 620411718 298766521 361324668 0 486834509 225447688 859904884
628902494 755031424 713892371 722757772 69837030 486834509 0 434140395 490910900
596982638 86416231 272961036 623807668 222135106 225447688 434140395 0 22078599
853214705 284114341 836365490 366719378 935147464 859904884 490910900 22078599 0
20
9 7
8 9
9 8
7 6
9 8
8 9
9 7
7 8
7 8
6 9
9 8
9 6
8 6
8 9
6 8
8 7
7 6
8 9
7 6
9 6

示例输出 2

849002970
779165940
779165940
882119751
779165940
779165940
849002970
826924371
826924371
834361320
779165940
834361320
812282721
779165940
812282721
826924371
882119751
779165940
882119751
834361320