Factorio - 题解

标签与难度

标签: 图论, 拓扑排序, 有向无环图(DAG), 高精度计算, 模拟, 数据结构 难度: 2100

嘿，是题目大意喵~

你好呀，指挥官！今天我们来到了一家叫做 Factorio 的神奇工厂，这里的一切都遵循着精确的生产配方，喵~。

工厂里有各种各样的物品，可以分为三类：

1. 自然资源: 像铁矿石、铜矿石一样，是从地里挖出来的，是所有生产链的最开端。它们只能被用作原料。
2. 中间产品: 由一些原料（可能是自然资源或其他中间产品）通过装配机合成。比如用铜可以造出电缆。
3. 最终产品: 整个工厂的目标！它是唯一一种不会被用来制造其他任何东西的产品。

每个物品的生产都由装配机或采矿机负责。我们手头有一份清单，记录了每种物品有多少台专属的生产机器。

生产关系由一系列配方决定，形如： c1 原料1 + c2 原料2 + ... = c_p 产品p 这意味着需要 c1 份原料1，c2 份原料2... 才能合成出 c_p 份产品p。

我们的任务是找出工厂的 “生产瓶颈”。这是个什么概念呢？喵~？ 简单来说，瓶颈就是那些最最最限制我们最终产品产量的物品。如果我们给这些瓶颈物品增加一台生产机器，整个工厂的最高生产效率就能得到提升。反之，如果给非瓶颈物品增加机器，则完全没用，因为有其他东西限制得更厉害。

我们要做的就是，根据给定的机器数量和生产配方，找出所有构成这个“生产瓶颈”的物品，并按字母顺序列出它们。

解题思路分析

这道题看起来有点复杂，信息量好大呀，喵~！不过别怕，让我来把问题拆解成一小块一小块的猫爪饼干，我们一块一块吃掉它！

1. 把工厂抽象成一张图

首先，物品之间的生产关系，天然就是一张有向图！每个物品（无论是资源、中间产品还是最终产品）都是图上的一个节点。

如果物品 A 是生产物品 B 的直接原料，我们就可以连一条从 B 到 A 的有向边 B -> A。这表示“想要B，就得先有A”。这样一来，整个工厂的生产流程就变成了一张巨大的有向无环图（DAG）。为什么是无环的呢？因为一个产品总不能自己生产自己吧，那不成永动机了，喵~。

在这张图里：

• 自然资源 是那些没有入边的节点（它们不是由其他物品生产的）。
• 最终产品 是那个唯一的、没有出边的节点（它不被用于生产任何其他东西）。

2. 量化需求：生产一个最终产品需要多少原料？

要找到瓶颈，我们得先知道为了生产一个单位的最终产品，到底需要多少单位的各种其他物品。我们把这个需求量叫做 demand[i]，表示生产 1 个最终产品需要 demand[i] 个物品 i。

怎么计算这个 demand 值呢？这是一个从最终产品向前追溯的过程。

• 对于最终产品 FP，它的需求量显然是 demand[FP] = 1。
• 对于任何一个物品 u，假设它是生产物品 v 的原料之一，配方是 ... + c_u * u + ... = c_v * v。这意味着，每当我们需要 c_v 个 v 时，就需要 c_u 个 u。换句话说，对 v 的每单位需求，会产生对 u 的 c_u / c_v 单位的需求。
• 所以，一个物品 u 的总需求量，是所有“下游”产品对它产生的需求之和。

  \text{demand}[u] = \sum_{v \text{ where } u \text{ is a material for } v} \text{demand}[v] \times \frac{\text{count_of_u_for_v}}{\text{count_of_v_produced}}

这个计算过程是不是很像在图上反向传播？我们可以从最终产品开始，沿着图的边反向（从产品到原料）进行计算。这可以通过在反向图上进行拓扑排序来实现。一个更直观的方法是：

1. 建立 产品 -> 原料 的图 G。同时记录每个物品被多少种更高级的产品当作原料，我们称之为 usage_count[i] (这其实就是反图的入度，或者原图的出度)。
2. 找到最终产品 FP（usage_count[FP] == 0 的那个节点）。
3. 初始化一个队列，把 FP 放进去。
4. 当队列不为空时，取出队首节点 u。对于 u 的每一种原料 v (即 u -> v): a. 根据配方，更新 v 的需求：demand[v] += demand[u] * (c_v / c_u)。 b. v 的一个“下游”已经被我们计算完了，所以 usage_count[v]--。 c. 如果 usage_count[v] 减到 0，说明所有需要 v 的产品都已被处理，v 的总需求已经计算完毕。此时，就可以把 v 加入队列，去更新它的上游原料了。

这个过程本质上就是反向的拓扑排序，喵~

3. 处理精度问题：烦人的分数！

注意到 c_v / c_u 可能会产生分数！比如 1 铜 = 2 电缆，那么1个电缆就需要 1/2 个铜。如果一路算下去，会有一大堆分数运算。用 double 或 float 肯定会因为精度问题而出错。

怎么办呢？有两个好办法：

1. 分数类: 像 Python 的 fractions.Fraction 一样，自己实现一个分数类来处理运算。
2. 高精度整数 (BigNum): 这是一个更稳妥的办法。我们可以把所有数都乘上一个巨大的公分母，把分数计算变成整数计算。比如，我们可以不设 demand[FP] = 1，而是设 demand[FP] 为一个非常大的数，比如 2^N（因为配方中的系数都是1或2，分母都是2的幂次，乘上一个大的2的幂次可以保证大部分时候是整数）。这样，在计算 demand[u] * c_v / c_u 时，我们就在用高精度整数进行计算，完美避免了精度损失！

从参考代码来看，使用高精度整数是可行的，我也更喜欢这种一力降十会的暴力美学，喵哈哈！

4. 找到真正的瓶颈！

现在我们有了每个物品 i 的总需求量 demand[i]。接下来就要结合工厂里每种物品的机器数量 a[i] 来找到瓶颈了。

• 供应能力: 假设生产物品 i 的配方一次能产出 c_i 个，而我们有 a[i] 台机器。那么物品 i 的最大供应能力就是 a[i] * c_i。（对于自然资源，c_i 可以看作1）。
• 需求压力: 为了生产1个最终产品，我们需要 demand[i] 个物品 i。
• 瓶颈因子: 我们可以定义一个“瓶颈因子” L[i] = demand[i] / (a[i] * c_i)。这个值代表了“单位供应能力需要支撑多少需求”。这个值越大，说明这个物品的压力越大，越接近瓶颈。

所以，生产瓶颈就是那些瓶颈因子 L[i] 最大的物品集合。

为了比较两个物品 i 和 j 的瓶颈因子大小，即比较 demand[i] / (a[i] * c_i) 和 demand[j] / (a[j] * c_j)，我们可以使用交叉相乘来避免高精度数的除法： 比较 demand[i] * a[j] * c_j 和 demand[j] * a[i] * c_i 的大小即可。

算法总结

好啦，梳理一下我们的爪印🐾：

1. 数据预处理: 读取输入，用 std::map 把物品名字映射到整数ID。建立产品 -> 原料的图，并记录每个物品的usage_count。
2. 计算需求:
   • 找到最终产品 FP。
   • 初始化 demand[FP] 为一个足够大的高精度数（如 2^N），其余为0。
   • 使用队列进行反向拓扑排序，从 FP 开始，计算出所有物品的 demand[i]。
3. 定位瓶颈:
   • 遍历所有物品，通过交叉相乘找到具有最大“瓶颈因子”的物品。
   • 再次遍历所有物品，把所有瓶颈因子与最大值相等的物品都找出来。
4. 输出结果: 将找到的瓶颈物品的名字按字典序排序后输出。

这样，问题就解决啦！是不是感觉清晰多了呢？喵~

代码实现

这是我根据上面的思路，重新整理的一份清晰易懂的代码哦~ 附上了详细的注释，希望能帮到你！

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <algorithm>

// --- Start of BigNum Class ---
// 一个简化版的高精度整数类，只包含本题需要的操作
// 为了简洁，这里直接使用 vector<int> 并采用万进制
struct BigNum {
    std::vector<int> digits;
    static const int BASE = 10000;

    BigNum(long long n = 0) {
        if (n == 0) {
            digits.push_back(0);
        }
        while (n > 0) {
            digits.push_back(n % BASE);
            n /= BASE;
        }
    }

    BigNum operator+(const BigNum& other) const {
        BigNum result;
        result.digits.clear();
        int carry = 0;
        for (size_t i = 0; i < digits.size() || i < other.digits.size() || carry; ++i) {
            int current = carry;
            if (i < digits.size()) current += digits[i];
            if (i < other.digits.size()) current += other.digits[i];
            result.digits.push_back(current % BASE);
            carry = current / BASE;
        }
        return result;
    }

    BigNum operator*(int n) const {
        BigNum result;
        result.digits.clear();
        long long carry = 0;
        for (size_t i = 0; i < digits.size() || carry; ++i) {
            long long current = carry;
            if (i < digits.size()) current += (long long)digits[i] * n;
            result.digits.push_back(current % BASE);
            carry = current / BASE;
        }
        while (result.digits.size() > 1 && result.digits.back() == 0) {
            result.digits.pop_back();
        }
        return result;
    }

    BigNum operator/(int n) const {
        BigNum result;
        result.digits.resize(digits.size());
        long long remainder = 0;
        for (int i = digits.size() - 1; i >= 0; --i) {
            remainder = remainder * BASE + digits[i];
            result.digits[i] = remainder / n;
            remainder %= n;
        }
        while (result.digits.size() > 1 && result.digits.back() == 0) {
            result.digits.pop_back();
        }
        return result;
    }

    // 比较函数: a > b 返回 1, a < b 返回 -1, a == b 返回 0
    int compare(const BigNum& other) const {
        if (digits.size() != other.digits.size()) {
            return digits.size() > other.digits.size() ? 1 : -1;
        }
        for (int i = digits.size() - 1; i >= 0; --i) {
            if (digits[i] != other.digits[i]) {
                return digits[i] > other.digits[i] ? 1 : -1;
            }
        }
        return 0;
    }
};
// --- End of BigNum Class ---

struct Material {
    int id;
    int count;
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m;
    while (std::cin >> n >> m) {
        std::map<std::string, int> name_to_id;
        std::vector<std::string> id_to_name(n);
        std::vector<int> machine_count(n);
        
        for (int i = 0; i < n; ++i) {
            std::cin >> id_to_name[i] >> machine_count[i];
            name_to_id[id_to_name[i]] = i;
        }

        std::vector<std::vector<Material>> recipes(n);
        std::vector<int> product_yield(n, 1); // 默认为1，对自然资源也适用
        std::vector<int> usage_count(n, 0); // 物品作为原料被使用的次数

        for (int i = 0; i < m; ++i) {
            std::vector<Material> current_materials;
            int count;
            std::string name;
            char op;

            while (std::cin >> count >> name) {
                current_materials.push_back({name_to_id[name], count});
                std::cin >> op;
                if (op == '=') break;
            }
            
            int product_id = current_materials.back().id;
            int product_count = current_materials.back().count;
            current_materials.pop_back();

            recipes[product_id] = current_materials;
            product_yield[product_id] = product_count;

            for (const auto& mat : current_materials) {
                usage_count[mat.id]++;
            }
        }

        // 2. 计算需求
        int final_product_id = -1;
        for (int i = 0; i < n; ++i) {
            if (usage_count[i] == 0) {
                final_product_id = i;
                break;
            }
        }

        std::vector<BigNum> demand(n, BigNum(0));
        // 设置一个足够大的初始值以避免分数
        BigNum base_val(1);
        for(int i = 0; i < n; ++i) base_val = base_val * 2;
        demand[final_product_id] = base_val;

        std::queue<int> q;
        q.push(final_product_id);

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            for (const auto& material : recipes[u]) {
                int v = material.id;
                int material_c = material.count;
                int product_c = product_yield[u];
                
                demand[v] = demand[v] + (demand[u] * material_c / product_c);
                
                usage_count[v]--;
                if (usage_count[v] == 0) {
                    q.push(v);
                }
            }
        }

        // 3. 定位瓶颈
        std::vector<int> bottleneck_candidates;
        int max_bottleneck_id = 0;

        for (int i = 1; i < n; ++i) {
            // 比较 i 和 max_bottleneck_id 谁更是瓶颈
            // 比较 demand[i] / (a[i]*c[i]) 和 demand[j] / (a[j]*c[j])
            // 等价于比较 demand[i] * a[j]*c[j] 和 demand[j] * a[i]*c[i]
            BigNum val_i = demand[i] * machine_count[max_bottleneck_id] * product_yield[max_bottleneck_id];
            BigNum val_j = demand[max_bottleneck_id] * machine_count[i] * product_yield[i];
            
            if (val_i.compare(val_j) > 0) {
                max_bottleneck_id = i;
            }
        }

        for (int i = 0; i < n; ++i) {
            BigNum val_i = demand[i] * machine_count[max_bottleneck_id] * product_yield[max_bottleneck_id];
            BigNum val_j = demand[max_bottleneck_id] * machine_count[i] * product_yield[i];
            if (val_i.compare(val_j) == 0) {
                bottleneck_candidates.push_back(i);
            }
        }

        // 4. 输出结果
        std::vector<std::string> result_names;
        for (int id : bottleneck_candidates) {
            result_names.push_back(id_to_name[id]);
        }
        std::sort(result_names.begin(), result_names.end());
        
        std::cout << result_names.size() << "\n";
        for (size_t i = 0; i < result_names.size(); ++i) {
            std::cout << result_names[i] << (i == result_names.size() - 1 ? "" : " ");
        }
        std::cout << "\n";
    }
    return 0;
}

复杂度分析

• 时间复杂度: $O((N+M_{total}) \cdot L)$

  • $N$ 是物品种类数， $M$ 是配方数。设 $M_{total}$ 是所有配方中原料项的总数。
  • 预处理（建图等）的时间是 $O(N + M_{total})$。
  • 计算 demand 的拓扑排序过程，每个节点和每条边（依赖关系）被访问一次。每次访问涉及高精度数的加法、乘法和除法。设高精度数的平均长度为 $L$，这些操作的复杂度是 $O(L)$。所以这部分的复杂度是 $O((N+M_{total}) \cdot L)$。
  • 寻找瓶颈需要 $O(N)$ 次比较，每次比较是两次高精度乘法，复杂度是 $O(L)$。所以这部分是 $O(N \cdot L)$。
  • 高精度数的长度 $L$ 最坏情况下和 $N$ 相关，因为路径最长为 $N$，每次乘2或除2，长度会增长。所以 $L$ 可以看作 $O(N)$。
  • 综合来看，总时间复杂度主要由计算 demand 的过程决定，约为 $O((N+M_{total}) \cdot L)$。

• 空间复杂度: $O(N \cdot L + M_{total})$

  • 存储图、配方等信息需要 $O(N + M_{total})$ 的空间。
  • demand 数组存储了 $N$ 个高精度数，每个长度为 $L$，所以需要 $O(N \cdot L)$ 的空间。
  • 因此，总空间复杂度为 $O(N \cdot L + M_{total})$。

知识点总结

这道题真是一次有趣的工厂冒险，喵~ 从中我们可以学到：

1. 图论建模: 将复杂的生产关系抽象为有向无环图（DAG）是解决问题的关键第一步。
2. 拓扑排序: 对于DAG上的依赖计算问题，拓扑排序（或其变体，如本题中的反向计算）是非常有效的工具。
3. 高精度计算: 当遇到会产生分数的计算且精度要求高时，要果断使用高精度整数（BigNum）或分数类来避免double带来的误差。
4. 交叉相乘: 这是一个比较两个分数大小的常用技巧，可以避免高精度数之间难以实现的除法运算。
5. 问题分解: 面对一个复杂的问题描述，不要慌张，把它拆解成数据结构建立、核心逻辑计算、结果查找等几个小步骤，逐一攻克，就能找到通往AC的道路啦！

希望这篇题解能让你有所收获，喵~ 下次再一起探险吧！