题目理解

我们有 $n$ 种物品，$m$ 种转化规则：

• 规则 $i$：$a_i \to \{b_{i,1}, b_{i,2}, \dots, b_{i,k_i}\}$
• 初始拥有 $c_i$ 个第 $i$ 种物品
• 转化可以无限次使用

对于每种物品 $d$，求最多能获得多少个，如果可以无限获得则输出 infinity。

---

问题分析

这是一个有向图上的资源转化问题，核心挑战在于：

1. 检测无限循环：某些转化可能产生指数增长
2. 计算最大产量：在有限情况下精确计算
3. 处理强连通分量：将图缩点为 DAG

---

代码解法详解

1. 图模型构建

将问题建模为有向图：

• 节点 $1$ 到 $n$：物品节点
• 节点 $n+1$ 到 $n+m$：转化规则节点
• 边：$a_i \to (n+i)$ 和 $(n+i) \to b_{i,j}$

for (int i = 1; i <= m; i++) {
    G[a[i]].pb(n + i);           // 物品 -> 规则
    for (int j = 0; j < k; j++) {
        G[n + i].pb(b[i][j]);    // 规则 -> 产出物品
    }
}

2. Tarjan 强连通分量缩点

void Tarjan(int x) {
    // 标准 Tarjan 算法
    // 将原图缩成 DAG，每个 SCC 记录：
    // - tc[cnt]: 该 SCC 中初始物品总数
    // - siz[cnt]: SCC 大小
    // - sd[u]: 节点 u 所属的 SCC 编号
}

3. 无限性检测

检测三种会产生无限资源的情况：

情况1：自环增长

for (int i = 1; i <= m; i++) {
    if (!zro[sd[n + i]]) {  // 如果该规则可达初始资源
        int tot_c = 0;
        for (auto j : b[i]) 
            tot_c += (sd[j] == sd[n + i]);  // 统计自环数
        if (tot_c >= 2)     // 如果产生 ≥2 个自身
            inf[sd[n + i]] = 1;
    }
}

情况2：间接无限增长

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        int tmp = 0;
        for (int tb : b[j]) {
            if (sd[tb] == v) tmp |= 1;      // 产生自身
            if (sd[tb] != v && r[sd[tb]][u]) tmp |= 2; // 产生可达资源
        }
        if (tmp == 3) {  // 既能产生自身又能产生可达资源
            inf[u] = 1;
            break;
        }
    }
}

4. 有限情况计算

在 DAG 上进行动态规划：

auto ord = topo();  // 拓扑排序
for (int i = 0; i < cnt; i++) {
    int u = ord[i];
    if (zro[u] || inf[u]) continue;
    
    memset(f, 0, sizeof(f));
    f[u] = 1;  // 基准单位
    
    // 向后传递计算转化系数
    for (int j = i + 1; j < cnt; j++) {
        int v = ord[j];
        if (siz[v] != 1 || !ds[v]) continue;
        
        v = ds[v] - n;  // 规则编号
        __int128 tf = 0;
        for (auto tb : b[v])
            tf += f[sd[tb]];  // 累加产出系数
        
        f[sd[a[v]]] = max(f[sd[a[v]]], tf);  // 更新输入系数
    }
    
    // 计算总产量 = Σ(初始数量 × 转化系数)
    for (int j = 1; j <= cnt; j++) {
        ans[u] += tc[j] * f[j];
    }
}

---

算法流程

1. 建图：物品节点 + 规则节点
2. 缩点：Tarjan 求 SCC，转化为 DAG
3. 无限检测：
   • 检查自环增长（产生 ≥2 个自身）
   • 检查间接增长（产生自身 + 可达资源）
4. 有限计算：
   • 拓扑排序 DAG
   • DP 计算每个 SCC 的转化系数
   • 乘以初始数量得到最大产量
5. 输出：根据检测结果输出 0、infinity 或具体数值

---

样例分析

对于样例：

n=4, m=4
初始: [1,0,0,0]
规则:
1 → {2,4}
1 → {3}  
2 → {4}
3 → {4}

计算过程：

• 物品1：初始1个，无增长 → 1
• 物品2：1→2 → 1
• 物品3：1→3 → 1
• 物品4：1→{2,4}, 2→4 → 1+1 = 2

与样例输出一致。

---

复杂度分析

• Tarjan：$O(n+m)$
• 无限检测：$O(m \cdot k + n \cdot m)$
• 拓扑排序：$O(n+m)$
• DP计算：$O(\text{SCC}^2 \cdot m)$
• 由于 $n \le 100, m \le 1000$，完全可行

---

算法标签

• 强连通分量
• 图论建模
• 动态规划
• 无限性检测
• 拓扑排序
• DAG

---

总结

这道题的解法核心是：

1. 图模型：将转化规则建模为二分图（物品-规则）
2. SCC缩点：处理循环依赖，转化为DAG
3. 无限检测：识别指数增长模式
4. 系数传递：在DAG上计算最大转化效率

通过巧妙的图论建模和分类处理，同时解决了有限计算和无限检测两个关键问题。