B4093 [CSP-X2021 山东] 发送快递

Question

在洛谷上，有一道难题把我难倒，名字B4093 [CSP-X2021 山东] 发送快递，请给我写题解，给出正确代码

Answer 1

让 “紫雾凌寒” 来帮你回答,本回答结合 DeepSeek

如果还有问题，请评论或点击头像私信，如果有帮助到您, 请关注、采纳、点赞

1. 问题关键点分析

• 这道题主要涉及到如何根据给定的快递重量、快递员承载重量以及快递点和配送点之间的关系，来确定最少需要多少名快递员才能完成所有快递的配送。
• 关键在于理解快递之间的分组方式以及如何利用快递员的承载能力来优化分组，从而达到最少快递员数量的目的。

2. 解决方案

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m, k;
int w[N];
vector<int> g[N];
bool st[N];

int dfs(int u) {
    st[u] = true;
    int sum = w[u];
    for (int v : g[u]) {
        if (!st[v]) {
            sum += dfs(v);
        }
    }
    return sum;
}

int main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
    }
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    int res = 0;
    for (int i = 1; i <= n; i++) {
        if (!st[i]) {
            int totalWeight = dfs(i);
            if (totalWeight <= k) {
                res++;
            } else {
                int num = (totalWeight + k - 1) / k;
                res += num;
            }
        }
    }

    cout << res << endl;

    return 0;
}

3. 代码解释

• 输入部分：
  cpp cin >> n >> m >> k; for (int i = 1; i <= n; i++) { cin >> w[i]; } for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; g[a].push_back(b); g[b].push_back(a); }
  • 读取快递数量 n，快递点之间的道路数量 m，以及每个快递员的承载重量 k。
  • 读取每个快递的重量 w[i]。
  • 读取快递点之间的道路连接关系，并存储在邻接表 g 中。
• 深度优先搜索部分：
  cpp int dfs(int u) { st[u] = true; int sum = w[u]; for (int v : g[u]) { if (!st[v]) { sum += dfs(v); } } return sum; }
  • 用于计算以节点 u 为根的子树中所有快递的总重量。
  • 标记当前节点 u 已访问，然后遍历其所有邻居节点 v，如果 v 未访问，则递归计算以 v 为根的子树重量并累加到 sum 中。
• 计算快递员数量部分：
  cpp int res = 0; for (int i = 1; i <= n; i++) { if (!st[i]) { int totalWeight = dfs(i); if (totalWeight <= k) { res++; } else { int num = (totalWeight + k - 1) / k; res += num; } } }
  • 遍历所有节点，如果节点未访问，则调用 dfs 计算该子树的总重量 totalWeight。
  • 如果总重量小于等于快递员承载重量 k，则只需要一名快递员，res 加1。
  • 否则，计算需要的快递员数量 num，并累加到 res 中。这里 (totalWeight + k - 1) / k 是向上取整的操作，确保能够承载所有重量。
• 输出结果：
  cpp cout << res << endl;
  • 输出最少需要的快递员数量。

4. 总结

• 这道题的核心思路是通过深度优先搜索来确定每个连通块内快递的总重量，然后根据快递员的承载能力来计算每个连通块需要的快递员数量，最后累加得到总的快递员数量。
• 代码通过邻接表存储图的结构，利用深度优先搜索遍历每个连通块，根据重量和承载能力的关系进行计算，最终输出结果。这种方法能够有效地解决快递分组配送的问题。

希望以上解答对您有所帮助。如果您有任何疑问，欢迎在评论区提出。