AT_abc395_g.[ABC395G] Minimum Steiner Tree 2

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定正整数 $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,\ldots,N$ 。对于满足 $i < j$ 的顶点对 $i,j$ ，连接顶点 $i$ 和 $j$ 的边的权重为 $C_{i,j}$ 。

给定 $Q$ 个查询。第 $i$ 个查询给出两个不同的整数 $s_i, t_i$ （ $K+1 \leq s_i, t_i \leq N$ ），请对每个查询回答以下问题：

从该图中移除任意数量的边和顶点后，得到的连通子图若包含顶点 $1,2,\ldots,K,s_i,t_i$ ，则称其为良构子图。

良构子图的成本定义为子图中所有边的权重之和。

求良构子图的最小成本。

输入格式

输入通过标准输入给出，格式如下：

$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

输入#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

说明/提示

约束条件

$3 \leq N \leq 80$
$1 \leq K \leq \min(N-2, 8)$
$0 \leq C_{i,j} \leq 10^9$ （ $1 \leq i,j \leq N$ 且 $i \neq j$ ）
$C_{i,j} = C_{j,i}$ （ $1 \leq i,j \leq N$ 且 $i \neq 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 \neq t_i$ （ $1 \leq i \leq Q$ ）
输入均为整数

样例解释 1

第一个查询：最优方案保留顶点 $1,2,3,4,5$ 和边 $1-4,2-3,3-5,4-5$ ，成本为 $4$ 。
第二个查询：最优方案保留顶点 $1,2,3,5$ 和边 $1-5,2-3,3-5$ ，成本为 $3$ 。

翻译由 DeepSeek R1 完成

输入解题思路，AI测评打分。不知道怎么写?

首页