HDU 3812 Sea Sky：DFS + 強力剪枝求最長路徑

問題描述

給定若干字符串對，視為無向圖的邊。從 "sea" 走到 "sky"，尋找最長簡單路徑（不重複節點）。若不存在路徑或 "sea"/"sky" 缺失，輸出 "what a pity"。多測試用例。

預處理與建圖

1. 收集所有唯一字符串，映射為 0~w-1 編號。
2. 按字典序排序 → DFS 先搜字典序小的鄰居，首個完整路徑即為字典序最小解。
3. 建立鄰接矩陣 mm[u][v]。
4. 並查集檢查 "sea" 與 "sky" 連通性，不連通直接輸出 "what a pity"。

關鍵剪枝策略

• 雙向可達性剪枝：對每個節點 i，若從 "sea" 不能到達 i 再到 "sky"（或反向），則 i 必不在任何合法路徑上，標記 vis[i]=1 永久禁用。
• 遞歸深度限制：tt >= w 直接返回。
• 字典序優先：鄰接表按排序後順序遍歷，找到長度 w-1（漢密爾頓路徑）即可提前結束。

核心 DFS

int dfs(int now, int tt) {
    if (tt >= w) return 0;
    vis[now] = 1; record[tt] = now;
    if (now == et) {
        if (ansl < tt) { ansl = tt; memcpy(yes, record, sizeof(record)); }
        if (tt == w - 1) return 1; // 找到最長可能
    }
    for (int i = 0; i < w; i++)
        if (!vis[i] && mm[now][i]) {
            vis[i] = 1;
            if (dfs(i, tt + 1)) return 1;
            vis[i] = 0;
        }
    return 0;
}

完整代碼結構

#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <map> #include <algorithm>
using namespace std;
char real[105][30]; int n, w, mm[105][105], st, et;
char temp1[208][30]; int record[105], vis[105], vis1[105];
int yes[105], root[105];
int Find(int r) { return r == root[r] ? r : root[r] = Find(root[r]); }
int add(char *a) { for (int i = 0; i < w; i++) if (strcmp(a, real[i]) == 0) return i; strcpy(real[w++], a); return w - 1; }
void init() { /* 讀邊、去重、排序、建圖、並查集 */ }
int dfs1(int ttt, int ending) { /* 可達性檢查 */ }
int main() {
    int cc, Case = 0; scanf("%d", &cc);
    while (cc--) {
        Case++; scanf("%d", &n);
        memset(vis, 0, sizeof(vis)); memset(mm, 0, sizeof(mm)); w = 0;
        init();
        for (int i = 0; i < w; i++) {
            if (strcmp(real[i], "sea") == 0) st = i;
            if (strcmp(real[i], "sky") == 0) et = i;
        }
        printf("Case %d:", Case);
        if (st == -1 || et == -1 || Find(st) != Find(et)) { puts(" what a pity"); continue; }
        for (int i = 0; i < w; i++) { memset(vis1, 0, sizeof(vis1)); vis1[st] = 1; if (!dfs1(i, et)) vis[i] = 1; }
        for (int i = 0; i < w; i++) { memset(vis1, 0, sizeof(vis1)); vis1[et] = 1; if (!dfs1(i, st)) vis[i] = 1; }
        ansl = 0; dfs(st, 0);
        for (int i = 0; i <= ansl; i++) printf(" %s", real[yes[i]]); puts("");
    }
    return 0;
}

複雜度分析

• 節點數 w ≤ 200（每條邊貢獻 2 字符串，n ≤ 100）。
• 最長路徑為 NP-Hard，但剪枝極強，實測極快。
• 空間 O(w²) 鄰接矩陣。