您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

Ural 1500 Pass Licenses：狀態壓縮 + DFS 求最少執照數

編輯：C++ 入門

題目大意

N 個節點，M 條邊，K 種執照（K ≤ 20）。每條邊需要某些執照才能通行。從節點 0 到 1，求最少需要攜帶多少種執照，並輸出方案。

解法：狀態壓縮枚舉 + DFS 連通性檢查

K ≤ 20 ⇒ 狀態數 2ᴷ ≤ 1,048,576，可枚舉
每個狀態用二進制位表示是否擁有該執照
對每個狀態，構建子圖（僅保留擁有執照可通行的邊），DFS 檢查 0→1 連通
剪枝：當前執照數 ≥ 已找到最小值，跳過

完整代碼

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int MAXN = 35;
int mp[MAXN][MAXN];      // 邊所需執照掩碼
int vis[MAXN];
int ans_licenses[MAXN];
int n, m, k, best_cnt = 0x3f3f3f3f, best_mask;

void dfs(int u, int mask) {
    vis[u] = 1;
    if (u == 1) return;
    for (int v = 0; v < n; v++) {
        if ((mask & mp[u][v]) && !vis[v])  // 擁有通行所需執照
            dfs(v, mask);
    }
}

int main() {
    while (scanf("%d%d%d", &k, &n, &m) == 3) {
        memset(mp, 0, sizeof(mp));
        for (int i = 0; i < m; i++) {
            int u, v, c;
            scanf("%d%d%d", &u, &v, &c);
            mp[u][v] |= (1 << c);
            mp[v][u] = mp[u][v];
        }
        
        best_cnt = 0x3f3f3f3f;
        for (int mask = 0; mask < (1 << k); mask++) {
            // 剪枝：統計執照數
            int cnt = __builtin_popcount(mask);
            if (cnt >= best_cnt) continue;
            
            memset(vis, 0, sizeof(vis));
            dfs(0, mask);
            
            if (vis[1]) {  // 可達
                best_cnt = cnt;
                best_mask = mask;
            }
        }
        
        printf("%d\n", best_cnt);
        bool first = true;
        for (int i = 0; i < k; i++) {
            if (best_mask & (1 << i)) {
                if (!first) printf(" ");
                printf("%d", i);
                first = false;
            }
        }
        printf("\n");
    }
    return 0;
}