Codeforces 507E Breaking Good：BFS + DP 重構最短路徑

CF 507E「Breaking Good」要求在無向圖中找到從 1 到 n 的最短路徑，並最小化「需修復的壞路 + 需拆除的好路」總數。本文解析 BFS 計算最短距離、DP 記錄最大好路數、回溯重構路徑的完整流程。

問題建模

• 無向圖，n 點，m 條邊。
• 每條邊狀態：c=1 好路，c=0 壞路。
• 目標：選擇一條 1→n 的最短路徑（邊數最少），使「路徑上壞路數 + 非路徑上好路數」最小。
• 等價：在最短路徑中最大化好路數（因總好路數固定）。

算法流程

1. BFS 計算最短距離 dis[]

從 1 出發 BFS，記錄每點到 1 的最短邊數 dis[v]。同時建立圖的鄰接表。

2. DP 在最短路 DAG 上求最大好路數

僅考慮滿足 dis[v] == dis[u] + 1 的邊 (u,v)，構成最短路 DAG。DP 狀態：

• dp[v]：從 1 到 v 的最短路徑中最大好路數。
• pre[v]：實現該最大值的前驅節點。
• 遞推：dp[v] = max(dp[v], dp[u] + c) 對於所有滿足條件的 u。

3. 回溯確定最優路徑邊集

從 n 沿 pre[] 回溯到 1，標記路徑上的邊（用 map<pair<int,int>, int> 或雙向標記）。

4. 統計答案

• 遍歷所有邊：
• 若在路徑上且 c=0 → 需修復 (輸出 c=1)
• 若不在路徑上且 c=1 → 需拆除 (輸出 c=0)
• 其他情況無需操作

關鍵代碼片段（C++）

// BFS + DP 一體化
queue<int> q;
q.push(1);
dis[1] = 0; vis[1] = 1;
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (auto &e : G[u]) {
        int v = e.v, c = e.c;
        if (!vis[v]) {
            dis[v] = dis[u] + 1;
            vis[v] = 1;
            q.push(v);
        }
        // 僅在最短路 DAG 上鬆弛
        if (dis[v] == dis[u] + 1 && dp[u] + c >= dp[v]) {
            dp[v] = dp[u] + c;
            pre[v] = u;
        }
    }
}

// 回溯標記路徑邊
int v = n;
while (v != 1) {
    onPath[{v, pre[v]}] = onPath[{pre[v], v]} = 1;
    v = pre[v];
}

// 生成答案
for (int i = 0; i < m; ++i) {
    bool on = onPath[{x[i], y[i]}];
    if (on && c[i] == 0) ans.push_back({x[i], y[i], 1}); // 修復
    else if (!on && c[i] == 1) ans.push_back({x[i], y[i], 0}); // 拆除
}

複雜度分析

• BFS: O(n + m)
• DP 鬆弛: 每條邊最多處理 2 次 → O(m)
• 回溯與統計: O(n + m)
• 總時間: O(n + m)，空間: O(n + m)

關鍵細節

1. 邊雙向存儲：無向圖添加兩次有向邊。
2. DP 條件 >=：相等時也更新 pre，保證能回溯到任意一條最優路徑。
3. 邊標記用 pair：map<pair<int,int>, int> 或 unordered_map<long long, int> (key = (long long)u * N + v)。
4. 輸出順序無要求：任意順序均可。

總結

本題是「BFS 找最短路 + DP 在 DAG 上優化次要指標 + 回溯重構」的經典組合。核心洞察：將「最小化修改數」轉化為「最短路中最大化好路數」，從而將雙目標問題分解為標準最短路 + 線性 DP。這類「主目標約束下優化副目標」模式廣泛適用於圖論優化問題。