BZOJ 1179 [APIO2009] ATM：Tarjan 強連通分量縮點 + SPFA 最長路完整解析

問題建模

• 有向圖 N 點 M 邊，每點有權值 (ATM 金額)
• 從起點 S 出發，終點為 P 個酒吧節點之一
• 路徑上經過的節點權值累加 (可重複經過節點/邊)
• 求最大累加權值

核心洞察：強連通分量 (SCC) 縮點

在強連通分量內任意兩點互達，且可無限次遍歷。因此：

1. SCC 內所有節點權值可合併到代表點 (根節點)
2. 進入 SCC 即可獲得該分量所有權值
3. 將原圖縮點為 DAG (有向無環圖)，問題轉化為 DAG 上從起點到終點集的最長路

算法流程

1. Tarjan 算法 求所有 SCC，記錄每節點所屬分量根節點 father[u]
2. 權值合併：非根節點權值加到根節點 w[root] += w[u]
3. 重建圖：遍歷原邊，若 father[u] != father[v] 添加縮點後的邊
4. SPFA 求最長路：在 DAG 上從 father[S] 起跑 SPFA (隊列優化 Bellman-Ford)，距離數組 dist[v] = max(dist[v], dist[u] + w[v])
5. 答案提取：遍歷所有酒吧節點，取 max(dist[father[bar]])

關鍵代碼實現

Tarjan 核心

void tarjan(int u) {
    dfn[u] = low[u] = ++num;
    stack[++top] = u; inStack[u] = true;
    for (int i = hh[u]; i; i = b[i].next) {
        int v = b[i].v;
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (inStack[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) { // 找到 SCC 根
        inStack[u] = false;
        father[u] = u;
        while (stack[top] != u) {
            w[u] += w[stack[top]];
            father[stack[top]] = u;
            inStack[stack[top--]] = false;
        }
        top--;
    }
}

SPFA 最長路

void spfa() {
    memset(inQueue, 0, sizeof(inQueue));
    int h = 0, t = 0;
    q[++t] = s; dist[s] = w[s]; inQueue[s] = 1;
    while (h < t) {
        int u = q[++h]; inQueue[u] = 0;
        for (int i = hhh[u]; i; i = ss[i].next) {
            int v = ss[i].v;
            if (dist[u] + w[v] > dist[v]) {
                dist[v] = dist[u] + w[v];
                if (!inQueue[v]) {
                    q[++t] = v;
                    inQueue[v] = 1;
                }
            }
        }
    }
}

複雜度分析

• Tarjan：O(N + M)
• 重建圖：O(M)
• SPFA：DAG 上無負環，實際接近 O(N + M)，理論最壞 O(NM) 但數據範圍 (50萬點邊) 通常可通過
• 總體：線性級別，滿足題目限制

易錯點提醒

• 權值合併方向：非根 → 根，不可反向
• 重建圖去重：同一 SCC 間可能有多條邊，SPFA 可處理重邊但建議去重優化
• 起點轉換：s = father[s]，若起點在 SCC 內需用根節點
• 酒吧節點同理：查詢 dist[father[bar]]
• 數組大小：N, M ≤ 500,000，靜態數組開 510,000 以上

本題是「強連通分量縮點 + DAG 最長路」的經典模板題，掌握此模式可解決大類圖論優化問題。