题目分析与思路提示

1. 为什么不能用 Dijkstra？

Dijkstra 算法用于求最短路。在求最长路时，贪心策略失效（因为我们可以绕路去增加总长度，且没有负权边的限制概念）。 但在 DAG 中，我们可以利用其“无环”的特性，使用动态规划 (DP) 来解决。

2. 核心算法：记忆化搜索 (DFS + Memoization)

我们定义 $dp[u]$ 表示：从节点 $u$ 出发，能够走出的最长路径长度。

状态转移方程：

$$dp[u] = \max_{(u, v, w) \in Edges} \{ w + dp[v] \} $$

• 即：$u$ 往后走一步到 $v$，耗时 $w$，再加上从 $v$ 开始能走的最长路 $dp[v]$。
• 如果是出度为 0 的点（终点），$dp[u] = 0$。

算法流程：

1. 初始化 dp 数组为 -1（表示未计算）。
2. 遍历所有节点 $i$（从 1 到 $N$），分别调用 dfs(i) 计算从该点出发的最长路。
   • 注意：虽然我们要遍历所有点，但由于有记忆化，每个点只会被计算一次。
3. 在所有 dp[i] 中取最大值，即为答案。

或者使用拓扑排序：

1. 按拓扑序遍历节点。
2. 对于每个节点 $u$，更新它的所有邻居 $v$：dist[v] = max(dist[v], dist[u] + w)。

• 这两种方法等价，记忆化搜索写起来通常更简洁。

3. 复杂度分析

• 时间复杂度：每个节点只会被 dfs 计算一次，每条边只会被遍历一次。总复杂度 $O(N + M)$。对于 $10^5$ 的数据，线性时间非常快。
• 空间复杂度：邻接表和 DP 数组，均为 $O(N + M)$。

---

参考代码 (C++14)

/**
 * 题目：木牛流马的征途 (Longest Path in DAG)
 * 难度：GESP 6级
 * 算法：DAG DP (记忆化搜索)
 */

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

using namespace std;

// IO 优化
void fast_io() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
}

const int MAXN = 100005;

// 结构体存储边
struct Edge {
    int to;
    int weight;
};

vector<Edge> adj[MAXN];
long long dp[MAXN]; // dp[u] 存储从 u 出发的最长路径长度

// 记忆化搜索
long long dfs(int u) {
    // 1. 如果已经计算过，直接返回记忆的值
    if (dp[u] != -1) {
        return dp[u];
    }

    long long max_len = 0; // 如果没有出边，长度为 0

    // 2. 遍历所有出边，进行状态转移
    for (const auto& e : adj[u]) {
        // 从 v 出发的最长路 + 当前边权 w
        long long current_len = dfs(e.to) + e.weight;
        max_len = max(max_len, current_len);
    }

    // 3. 记录并返回
    return dp[u] = max_len;
}

int main() {
    fast_io();

    int N, M;
    if (!(cin >> N >> M)) return 0;

    for (int i = 0; i < M; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }

    // 初始化 dp 数组为 -1
    for (int i = 1; i <= N; ++i) {
        dp[i] = -1;
    }

    long long ans = 0;

    // 遍历每一个点，尝试作为起点
    // 由于是 DAG，最长路径的起点一定是入度为 0 的点（虽然从中间点搜也可以，结果会被包含）
    // 记忆化搜索会自动处理依赖关系
    for (int i = 1; i <= N; ++i) {
        ans = max(ans, dfs(i));
    }

    cout << ans << endl;

    return 0;
}

---

数据生成器 (Data Generator)

用于生成 1.in ~ 10.in 及其标准答案。 重点：生成 DAG 必须保证无环。最简单的方法是只允许 $u < v$ 的边，或者先生成一个随机排列（拓扑序），只允许排在前面的指向后面的。

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <numeric>
#include <queue>    // [修复] 必须包含：用于 queue
#include <tuple>    // [修复] 必须包含：用于 tuple, get
#include <random>   // [修复] 必须包含：用于 shuffle, default_random_engine

using namespace std;

// ------------------------------------------
// 标准解法函数 (生成 .out) - 防爆栈可改用非递归，但DAG一般用记忆化
// ------------------------------------------
const int MAXN = 100005;
struct E { int v, w; };
vector<E> g_adj[MAXN];
long long g_dp[MAXN];

long long dfs_solve(int u) {
    if (g_dp[u] != -1) return g_dp[u];
    long long mx = 0;
    for (auto& e : g_adj[u]) {
        mx = max(mx, dfs_solve(e.v) + e.w);
    }
    return g_dp[u] = mx;
}

long long solve(int N, const vector<tuple<int, int, int>>& edges) {
    for (int i = 1; i <= N; i++) {
        g_adj[i].clear();
        g_dp[i] = -1;
    }
    for (auto& e : edges) {
        g_adj[get<0>(e)].push_back({get<1>(e), get<2>(e)});
    }
    
    long long ans = 0;
    
    // --- 生成器内部求解逻辑 (拓扑排序) ---
    // 为了防止递归爆栈，这里使用非递归的拓扑排序DP
    vector<int> in_degree(N + 1, 0);
    for(auto& e : edges) in_degree[get<1>(e)]++;
    
    vector<long long> dist(N + 1, 0);
    queue<int> q;
    for(int k=1; k<=N; k++) if(in_degree[k] == 0) q.push(k);
    
    while(!q.empty()) {
        int u = q.front(); q.pop();
        ans = max(ans, dist[u]);
        for(auto& edge : g_adj[u]) {
            int v = edge.v;
            dist[v] = max(dist[v], dist[u] + edge.w);
            in_degree[v]--;
            if(in_degree[v] == 0) q.push(v);
        }
    }
    
    return ans;
}

// 辅助函数
int randRange(int min, int max) {
    return rand() % (max - min + 1) + min;
}

int main() {
    srand(time(0));
    
    cout << "Start generating data..." << endl;

    for (int i = 1; i <= 10; ++i) {
        string in_name = to_string(i) + ".in";
        string out_name = to_string(i) + ".out";
        ofstream fin(in_name);
        ofstream fout(out_name);

        int N, M;
        vector<tuple<int, int, int>> edges;

        // 构造测试点
        if (i == 1) { 
            // 样例1
            N = 5; M = 6;
            edges = {{1,2,2}, {1,3,5}, {2,4,10}, {2,5,3}, {3,5,4}, {4,5,2}};
        }
        else if (i == 2) {
            // 样例2 (链)
            N = 4; M = 3;
            edges = {{1,2,10}, {2,3,10}, {3,4,10}};
        }
        else if (i == 3) {
            // 菊花图 (1指向所有)
            N = 100; M = N-1;
            for(int k=2; k<=N; k++) edges.emplace_back(1, k, randRange(1, 100));
        }
        else if (i == 4) {
            // 稀疏随机 DAG
            N = 100; M = 200;
            for(int k=0; k<M; k++) {
                int u = randRange(1, N-1);
                int v = randRange(u+1, N); // 保证无环
                edges.emplace_back(u, v, randRange(1, 100));
            }
        }
        else if (i == 5) {
            // 稠密随机 DAG (M 接近 N^2/2)
            N = 50; M = 500;
            for(int k=0; k<M; k++) {
                int u = randRange(1, N-1);
                int v = randRange(u+1, N);
                edges.emplace_back(u, v, randRange(1, 100));
            }
        }
        else if (i == 6) {
            // 长链 (N=2000) 测试深度
            N = 2000; M = N-1;
            for(int k=1; k<N; k++) edges.emplace_back(k, k+1, 1);
        }
        else if (i == 7) {
            // 分层图 (Level Graph)
            N = 1000; M = 5000;
            // 节点按层分布，只允许层间连边
            for(int k=0; k<M; k++) {
                int u = randRange(1, N-10);
                int v = randRange(u+1, min(N, u+50)); // 只连向后面不远的点，形成多层
                edges.emplace_back(u, v, randRange(1, 1000));
            }
        }
        else {
            // 大规模随机 (N=10^5)
            N = 100000; 
            if (i == 8) M = 100000;
            else if (i == 9) M = 200000;
            else M = 200000;

            // 为了保证拓扑序随机，我们先生成一个随机排列映射
            vector<int> p(N + 1);
            iota(p.begin(), p.end(), 0);
            // 修复点：使用 shuffle 需要 <random> 和 <algorithm>
            shuffle(p.begin() + 1, p.end(), default_random_engine(time(0)));

            for(int k=0; k<M; k++) {
                // 逻辑上 u < v，实际上用 p[u] -> p[v]
                // 这样生成的图节点编号虽然乱序，但依然无环
                int u = randRange(1, N-10);
                int v = randRange(u+1, min(N, u+1000)); // 限制跨度，避免全是长边
                edges.emplace_back(p[u], p[v], randRange(1, 1000));
            }
            
            // 对于 Case 10，我们在最后强制加一条长链的逻辑结构，保证答案够大
            if (i == 10) {
                // 清空重造一条长链
                edges.clear();
                M = N - 1;
                for(int k=1; k<N; k++) edges.emplace_back(k, k+1, 1000);
            }
        }

        // 写入输入
        fin << N << " " << edges.size() << "\n";
        for (const auto& e : edges) {
            fin << get<0>(e) << " " << get<1>(e) << " " << get<2>(e) << "\n";
        }

        // 写入输出
        fout << solve(N, edges) << endl;

        fin.close();
        fout.close();
        cout << "Generated Case " << i << endl;
    }
    
    cout << "Done!" << endl;
    return 0;
}