BZOJ 1663 趕集：最短路 + DAG 最長路的雙重圖論建模

問題描述

N (≤ 400) 個商店，商店 i 在時刻 P_i 發禮物。從店 i 走到店 j 需 T_ij 時間 (不對稱)。約翰從店 1 時刻 0 出發，不經中轉直接走目標店。求最多能拿多少禮物。

核心建模：DAG 上的最長路

1. 按發禮物時間 P_i 排序，得到拓撲序
2. 若從 i 能趕上 j：P_i + T_{i,j} ≤ P_j，則連邊 i → j
3. 添加虛擬源點 0：P_0=0, T_{0,j}=T_{1,j}
4. 問題轉化：DAG 上從 0 出發的最長路（邊權均為 1）

SPFA 求最長路

由於邊權為正 (1)，且圖為 DAG（按時間排序保證），可用 SPFA 或拓撲序 DP。SPFA 實現簡單：

#include 
#include 
#include 
#include 
#include 
using namespace std;

struct Node { int pos, tim; bool operator<(const Node& o) const { return tim < o.tim; } } p[405];
int T[405][405];
vector adj[405];
int dist[405], inq[405];

int spfa(int n) {
    queue q;
    q.push(0); inq[0] = 1; dist[0] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u] = 0;
        for (int v : adj[u]) {
            if (dist[u] + 1 > dist[v]) {
                dist[v] = dist[u] + 1;
                if (!inq[v]) { inq[v] = 1; q.push(v); }
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) ans = max(ans, dist[i]);
    return ans;
}

int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        for (int i = 1; i <= n; ++i) { scanf("%d", &p[i].tim); p[i].pos = i; }
        sort(p+1, p+n+1);
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                scanf("%d", &T[i][j]);
        
        for (int i = 1; i <= n; ++i) T[0][i] = T[1][i];
        p[0].pos = p[0].tim = 0;
        
        for (int i = 0; i <= n; ++i) adj[i].clear();
        for (int i = 0; i <= n; ++i)
            for (int j = i+1; j <= n; ++j)
                if (p[i].tim + T[p[i].pos][p[j].pos] <= p[j].tim)
                    adj[i].push_back(j);
        
        memset(dist, 0, sizeof(dist));
        memset(inq, 0, sizeof(inq));
        printf("%d\n", spfa(n));
    }
    return 0;
}

關鍵優化

• 時間排序建 DAG：保證無環，SPFA 不會陷入死循環
• 虛擬源點 0：統一處理從店 1 出發
• 邊構建剪枝：只考慮 j > i (時間更晚)，邊數 ≤ N²/2

複雜度

• 排序：O(N log N)
• 建圖：O(N²)
• SPFA：O(N²) (DAG 上退化為拓撲 DP)
• 總體：O(N²)，N=400 極快