侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【Prim算法】城邦【蓝桥杯】

GabrielxD
2023-01-11 / 0 评论 / 0 点赞 / 190 阅读 / 738 字
温馨提示:
本文最后更新于 2023-01-11,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

城邦 - 蓝桥云课


小蓝国是一个水上王国, 有 2021 个城邦, 依次编号 1 到 2021。在任意两个城邦之间, 都有一座桥直接连接。

为了庆祝小蓝国的传统节日, 小蓝国政府准备将一部分桥装饰起来。

对于编号为 aabb 的两个城邦, 它们之间的桥如果要装饰起来, 需要的费 用如下计算: 找到 aabb 在十进制下所有不同的数位, 将数位上的数字求和。

例如, 编号为 2021 和 922 两个城邦之间, 千位、百位和个位都不同, 将这 些数位上的数字加起来是 (2+0+1)+(0+9+2)=14(2+0+1)+(0+9+2)=14。注意 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());
    }
}

0

评论区