「PA 2018」Heros 题解

问题分析

给定一个 DAG（有向无环图），我们可以删除 $k$ 个节点，目标是最小化删除后图中的最长路径长度。

关键约束：

• $n \leq 300$
• $m \leq 400$
• $k \leq \min(n, 4)$（$k$ 很小）

算法思路

核心思想：枚举 + DAG 最长路径

由于 $k$ 最大只有 $4$，我们可以枚举所有可能的删除方案，对每个删除后的图计算最长路径，取最小值。

算法步骤

1. 枚举所有删除方案：从 $n$ 个节点中选择 $k$ 个删除
2. 对每个删除方案：
   • 构建删除后的图
   • 计算该图的最长路径长度
3. 取所有方案的最小值作为答案

优化策略

• 拓扑排序：DAG 最长路径可以通过拓扑排序 + DP 在 $O(n+m)$ 时间内计算
• 组合数优化：当 $k=4$ 时，$C_{300}^4 \approx 3.7 \times 10^8$ 太大，需要进一步优化
• 增量计算：避免重复计算

C++ 代码实现

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

const int MAXN = 305;
const int INF = 1e9;

int n, m, k;
vector<int> graph[MAXN];
int indeg[MAXN], dist[MAXN];
bool removed[MAXN];
int original_indeg[MAXN];

// 预先计算拓扑序和DP值
void precompute(vector<int>& topo_order, vector<int>& dp) {
    vector<int> temp_indeg(n + 1);
    for (int i = 1; i <= n; i++) {
        temp_indeg[i] = original_indeg[i];
    }
    
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (!removed[i] && temp_indeg[i] == 0) {
            q.push(i);
        }
    }
    
    topo_order.clear();
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topo_order.push_back(u);
        
        for (int v : graph[u]) {
            if (removed[v]) continue;
            temp_indeg[v]--;
            if (temp_indeg[v] == 0) {
                q.push(v);
            }
        }
    }
    
    // 计算最长路径
    dp.assign(n + 1, 0);
    for (int u : topo_order) {
        for (int v : graph[u]) {
            if (removed[v]) continue;
            dp[v] = max(dp[v], dp[u] + 1);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m >> k;
    
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        graph[x].push_back(y);
        original_indeg[y]++;
    }
    
    int ans = INF;
    vector<int> topo_order, dp;
    
    // 同样的枚举结构，但使用预计算
    if (k == 0) {
        precompute(topo_order, dp);
        ans = *max_element(dp.begin(), dp.end());
    } else if (k == 1) {
        for (int i = 1; i <= n; i++) {
            removed[i] = true;
            precompute(topo_order, dp);
            ans = min(ans, *max_element(dp.begin(), dp.end()));
            removed[i] = false;
        }
    } 
    // ... 类似的k=2,3,4情况
    
    cout << ans << endl;
    
    return 0;
}

进一步优化思路

1. 剪枝：如果当前删除方案的最长路径已经大于当前答案，可以提前终止
2. 增量更新：利用之前计算的结果，避免重复计算
3. 随机化：当 $k=4$ 时，可以随机采样部分方案

算法标签

• DAG 上 DP
• 状态设计优化
• 拓扑排序

总结

本题的核心在于利用 $k$ 很小的特点，通过枚举所有可能的删除方案，对每个方案计算 DAG 的最长路径。虽然最坏情况下的复杂度较高，但在实际数据中通常可以接受。对于大规模数据，需要更复杂的优化策略。