题目
小蓝国是一个水上王国, 有 2021 个城邦, 依次编号 1 到 2021。在任意两个城邦之间, 都有一座桥直接连接。
为了庆祝小蓝国的传统节日, 小蓝国政府准备将一部分桥装饰起来。
对于编号为 和 的两个城邦, 它们之间的桥如果要装饰起来, 需要的费 用如下计算: 找到 和 在十进制下所有不同的数位, 将数位上的数字求和。
例如, 编号为 2021 和 922 两个城邦之间, 千位、百位和个位都不同, 将这 些数位上的数字加起来是 。注意 922 没有千位, 千位看成 0 。
为了节约开支, 小蓝国政府准备只装饰 2020 座桥, 并且要保证从任意一个 城邦到任意另一个城邦之间可以完全只通过装饰的桥到达。
请问, 小蓝国政府至少要花多少费用才能完成装饰。
提示: 建议使用计算机编程解决问题。
答案提交
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一 个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。
运行限制
- 最大运行时间:1s
- 最大运行内存: 256M
解题
方法一:最小生成树 Prim算法
思路
把该王国看成图,其有 2021 个顶点且每两个顶点之间都有一条边,那么这是一张完全图。装饰方案需要满足:具有该图所有点且边数为 2020 的连通子图,也就是生成树。我们需要求完成装饰至少要花的费用也就是总权重最小的生成树,即:最小生成树中的总权重。
综上所述,这题是稠密图求最小生成树,用Prim算法解决即可。
代码
import java.util.*;
import java.io.*;
public class Main {
static final int N = 2030, INF = 0x3f3f3f3f;
static int n = 2021;
static int[][] g = new int[N][N];
static boolean[] vis = new boolean[N];
static int[] dists = new int[N];
static int prim() {
Arrays.fill(dists, INF);
int res = 0;
for (int i = 0; i < n; ++i) {
int mn = -1;
for (int j = 1; j <= n; ++j) {
if (!vis[j] && (mn == -1 || dists[j] < dists[mn])) mn = j;
}
if (i != 0) {
if (dists[mn] == INF) return INF;
res += dists[mn];
}
vis[mn] = true;
for (int j = 1; j <= n; ++j) dists[j] = Math.min(dists[j], g[j][mn]);
}
return res;
}
public static void main(String[] args) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (i == j) {
g[i][i] = INF;
continue;
}
int x = i, y = j, w = 0;
while (x > 0 || y > 0) {
int a = x % 10, b = y % 10;
if (a != b) w += a + b;
x /= 10;
y /= 10;
}
g[i][j] = g[j][i] = w;
}
}
System.out.println(prim());
}
}
评论区