分数: 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