UVA 140：Bandwidth - 全排列暴力求最小帶寬

問題描述

給定圖 (≤8 個節點，大寫字母)，找節點排列使「帶寬」最小。帶寬定義為：所有邊的兩端點在排列中位置差的最大值。多解輸出字典序最小。

暴力全排列

節點數 ≤ 8，全排列數 ≤ 40320，可行。步驟：

1. 解析輸入構建鄰接矩陣 adj[26][26]，記錄出現的節點列表 nodes。
2. 對 nodes 排序，用 next_permutation 枚舉所有排列。
3. 對每個排列，計算帶寬：遍歷所有邊，求位置差最大值。
4. 記錄最小帶寬及對應排列 (字典序最小自動滿足，因初始排序並按字典序枚舉)。

代碼實現

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

int main() {
    string line;
    while (cin >> line, line != "#") {
        bool adj[26][26] = {};
        bool exist[26] = {};
        // 解析 line，格式如 "A:FB;B:GC;..."
        // 簡化：按 ';' 分割，再按 ':' 分割
        // ... 解析代碼略 ...
        vector nodes;
        for (int i = 0; i < 26; ++i) if (exist[i]) nodes.push_back('A'+i);
        sort(nodes.begin(), nodes.end());

        vector best = nodes;
        int min_bw = INT_MAX;
        do {
            int pos[26];
            for (int i = 0; i < nodes.size(); ++i) pos[nodes[i]-'A'] = i;
            int bw = 0;
            for (int u = 0; u < 26; ++u)
                for (int v = 0; v < 26; ++v)
                    if (adj[u][v])
                        bw = max(bw, abs(pos[u] - pos[v]));
            if (bw < min_bw) {
                min_bw = bw;
                best = nodes;
            }
        } while (next_permutation(nodes.begin(), nodes.end()));

        for (char c : best) cout << c << ' ';
        cout << "-> " << min_bw << '\n';
    }
    return 0;
}

關鍵點

• 輸入解析需處理 ; 分隔記錄，: 分隔節點與鄰居。
• next_permutation 要求初始序列有序，且按字典序生成，天然滿足「字典序最小」要求。
• 位置數組 pos 實現 O(1) 查詢節點在排列中的索引。

總結

小規模圖的最小帶寬問題，全排列暴力枚舉可行。關鍵在於輸入解析、字典序處理、位置差快速計算。