POJ 3249 Test for Job - 拓撲排序 DP 求最長路徑

題目模型

有向無環圖 (DAG)，節點有權值 v[i]。求從任意入度 0 點到任意出度 0 點的路徑最大權值和。

算法：拓撲序 DP

1. 計算入度，入度 0 入隊，dp[i] = v[i]
2. 拓撲序遍歷：dp[to] = max(dp[to], dp[u] + v[to])
3. 所有出度 0 點中取最大 dp 值

代碼實現

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int n, m, in[100010], out[100010], v[100010], dp[100010];
vector<int> e[100010];

void topo() {
    fill(dp, dp+n+1, -INF);
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (in[i] == 0) { dp[i] = v[i]; q.push(i); }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int to : e[u]) {
            dp[to] = max(dp[to], dp[u] + v[to]);
            if (--in[to] == 0) q.push(to);
        }
    }
}

int main() {
    while (~scanf("%d%d", &n, &m)) {
        fill(in, in+n+1, 0);
        fill(out, out+n+1, 0);
        for (int i = 1; i <= n; i++) e[i].clear();
        for (int i = 1; i <= n; i++) scanf("%d", &v[i]);
        for (int i = 0; i < m; i++) {
            int a, b; scanf("%d%d", &a, &b);
            e[a].push_back(b);
            in[b]++; out[a]++;
        }
        topo();
        int ans = -INF;
        for (int i = 1; i <= n; i++) if (out[i] == 0) ans = max(ans, dp[i]);
        printf("%d\n", ans);
    }
    return 0;
}

關鍵點

• 多源點、多匯點：入度 0 全部初始化，出度 0 全部檢查答案
• dp 初始化為 -INF 防止未到達節點干擾
• 邊數組 vector<int> e[maxn] 靜態分配避免重複構造