洛谷 P1113 [USACO02FEB] 杂务

// ★★ P1113 正解：**一遍扫过去就行 —— 连图都不用存。**
//
// 题面里那句话是全部关键：
//   「杂务 k (k > 1) 的准备工作**只可能在杂务 1 至 k−1 中**」
// ⇒ **输入本身就已经是一个拓扑序了。** 按 1 → n 的顺序处理，
//   每读到杂务 i，它的所有前置 j < i 早就算完了。
//
//     f[i] = len[i] + max(f[j])      j 是 i 的前置；没有前置就是 f[i] = len[i]
//     答案 = max(f[i])               ⚠ 不是 f[n]！见 p1113Last.cpp
//
// ⇒ ★★ 这是第 29 章那句话的另一面：**「选存法」里包括「不存」。**
//   前置关系读进来就地用掉，一条边都不留 —— 顶格连 1 KB 都不到，
//   而老老实实建图要存 10⁶ 条边（8 MB，见 p1113Topo.cpp）。
//
// ⚠ 输入是**变长行**：`序号 用时 前置… 0`。别去管换行，直接流式读到 0 为止。
// 规模：n ≤ 10⁴、len ≤ 100 ⇒ 答案 ≤ 10⁶，**int 绰绰有余**。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<int> f(n + 1, 0);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int id, len;
        cin >> id >> len;
        int best = 0;
        int p;
        while (cin >> p && p != 0) best = max(best, f[p]);   // ★ 前置早就算完了
        f[id] = best + len;
        ans = max(ans, f[id]);                               // ★★ 答案是全体的 max
    }
    printf("%d\n", ans);
    return 0;
}

// ✗ P1113 错法一：**把答案写成 f[n]** —— 而官方样例正好放过它。
//
// 「完成所有杂务的最短时间」= 所有杂务里最晚结束的那个，也就是 max(f[i])。
// 写成 f[n] 就是默认「最后一项一定最晚完成」—— 题面**一个字都没这么保证**。
//
// ★ 它解的是一个更小的问题（只要求做完第 n 项）⇒ 答案**恒 ≤ 正解**。
// ⚠ 而官方样例里 f[7] 恰好就是 23（第 7 项确实最晚），**样例挡不住它**。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<int> f(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        int id, len;
        cin >> id >> len;
        int best = 0, p;
        while (cin >> p && p != 0) best = max(best, f[p]);
        f[id] = best + len;
    }
    printf("%d\n", f[n]);                                    // ★ 这里
    return 0;
}

// ✗ P1113 错法二：`f[i] = len[i] + **Σ** f[前置]` —— 把「等所有前置都好」读成了「一件件排队做」。
//
// 题面写着「互相没有关系的杂务**可以同时工作**，而且工人要多少有多少」，
// 所以一项杂务的开工时刻是**所有前置里最晚的那个**（max），不是它们的总和。
//
// ★ 它给出的是一个**真做得完的排法**（把所有前置串起来做）⇒ 答案**恒 ≥ 正解**。
// ⚠ 而且它错得**离谱**：前置一多就指数级放大 —— 解析页第 ③ 步量了差多少。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<long long> f(n + 1, 0);
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        int id, len, p;
        cin >> id >> len;
        long long sum = 0;
        while (cin >> p && p != 0) sum += f[p];              // ★ 加，而不是 max
        f[id] = sum + len;
        ans = max(ans, f[id]);
    }
    printf("%lld\n", ans);
    return 0;
}