AT_maximum_2013_a 特別作戦

由于巨大生物“巨人”的出现，人类被迫离开了自己的家园，迁居到被城墙包围的居住区，从而暂时获得了安全。然而，大约 100 年后，拥有足以摧毁城墙力量的“超大型巨人”出现，人类再次面临危险。更糟糕的是，这个“超大型巨人”神出鬼没，无法预测何时何地会出现。 城墙内被划分为若干个地区。即使巨人入侵了某个地区，只要封锁该地区，就能防止其他地区受到波及。居民们希望修建一套道路网络，以便即使某个地区被入侵，也能在不经过该地区的情况下，在剩余的所有地区之间自由通行。 你的任务是，求出满足上述条件所需修建的最少道路数，以及修建这些道路所需的最小总费用。 输入格式如下： > $N$ $E_{1,2}$ $E_{1,3}$ ... $E_{1,N-1}$ $E_{1,N}$ $E_{2,3}$ $E_{2,4}$ ... $E_{2,N}$ : $E_{N-2,N-1}$ $E_{N-2,N}$ $E_{N-1,N}$ 1. 第 1 行给出整数 $N$，表示地区的数量。 - 保证 $2 \leq N \leq 15$。 2. 第 2 行到第 $N$ 行共 $N-1$ 行，每行用空格分隔的整数 $E_{i,j}$。 - $E_{i,j}$ 表示修建第 $i$ 个地区和第 $j$ 个地区之间道路的费用。 - 保证 $1 \leq E_{i,j} \leq 1,000,000$。 请输出满足“无论去掉哪一个地区，剩余所有地区之间都能互相到达”这一条件时，所需修建道路的最小数量，以及所需的最小总费用。输出一行，两个数之间用空格分隔。 例如输入： ``` 4 1 5 4 2 6 3 ``` 输出： ``` 4 10 ```

第 1 行包含一个整数 $N$，表示地区的数量。 接下来 $N-1$ 行，每行包含若干个整数 $E_{i,j}$，第 $i$ 行有 $N-i$ 个整数，表示修建第 $i$ 个地区与第 $j$ 个地区之间道路的费用（$j > i$）。

输出一行，包含两个整数，分别表示所需修建道路的最小数量和最小总费用。两个数之间用一个空格分隔。

- $N$ 的范围较小，可以考虑枚举所有可能的道路组合。 - 需要保证无论去掉哪一个地区，剩余的所有地区之间都能互相到达。 - 这等价于构造一个“2-连通图”，即任意去掉一个节点后图仍然连通。 - 可以考虑枚举所有边的组合，判断是否满足条件，并取最优解。 由 ChatGPT 4.1 翻译