UVA140 - Bandwidth （暴力dfs+排列+剪枝）

2019-11-08 19:59:19

字體：大中小

來源：轉載

供稿：網友

題目鏈接：

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_PRoblem&problem=76

題目大意

有一個圖，有n個節點 (n < 8) ，講這些節點排成一列。定義節點i的帶寬為與相鄰節點在排列中的最遠距離，所有節點的帶寬最大值為圖的帶寬。求將這些節點排列后，帶寬最小的一種排列方式。

解題過程：

這個題寫了兩遍，之前一次，寫了差不多一半了，不在狀態，感覺又很煩，于是直接不想寫了。今天網上狀態很好，正好切換下了命名規范，以后還是以下劃線分割好了，普通變量名和函數小寫，類首字母大寫。

這里把這道題放上來，是因為 get 了新知識，解答樹的剪枝，當一種情況已經預知到不符合條件的時候，就不需要繼續 dfs 下去了，直接舍棄，相當于剪掉了解答樹的一條分支。

題目分析：

先處理輸入數據，這里自己寫了兩個輔助函數，用來處理輸入數據和初始化一些變量。這里選擇用矩陣儲存圖，之前用鄰接表感覺太麻煩了，因為直接添加的話，可能有重邊。然后是類似紫書上面全排列示例程序那樣寫的 dfs 函數，需要注意的是剪枝，和標記。當一個節點還有m個相鄰的節點未分配時，如果 m >= k (當前取得的最小帶寬) 時就舍棄掉這種情況，因為就算后面 m 個節點和當前節點緊挨著，那么最小帶寬也是 m ，題目要求是最小字典序的所以等于 k 的情況也舍掉。另外如果一個節點的相鄰節點已經分配了，如果這兩個節點的距離大于等于 k 也舍棄掉，理由同上。每次嘗試后，都需要把標記撤回。

AC代碼：

#include<bits/stdc++.h>using namespace std;const int MAX = 30;bool edges[MAX][MAX];char raw_data[1123];int node_num, book_num[MAX];int pos[MAX], ans[MAX], k;void put(){ char result[112]; for (int i = 0; i < MAX; i++) { if (ans[i] != -1) result[ans[i]] = 'A'+i; } for (int i = 0; i < node_num; i++) printf("%c ", result[i]); printf("-> %d/n", k);}void add_edge(int l, int r){ int u = raw_data[l] - 'A'; for (int i = l+2; i <= r; i++) { int v = raw_data[i] - 'A'; edges[u][v] = 1; edges[v][u] = 1; }}void analysis(){ node_num = 0, k = 9999; memset(pos, -1, sizeof(pos)); memset(edges, 0, sizeof(edges)); memset(book_num, 0, sizeof(book_num)); int len = strlen(raw_data); int head = 0; for (int i = 0; i < len; i++) { if (isalpha(raw_data[i]) && book_num[raw_data[i]-'A'] == 0) { book_num[raw_data[i]-'A'] = 1; node_num++; } if (i == len-1 || raw_data[i+1] == ';') { add_edge(head, i); head = i+2; } }}void solve(int cur, int cnt){ if (cur == node_num) { if (cnt < k) { for (int i = 0 ; i < MAX; i++) ans[i] = pos[i]; k = cnt; return; } } else { for (int i = 0; i < MAX; i++) { if (!book_num[i] || pos[i] != -1) continue; pos[i] = cur; int dis = 0, flag = 1; for (int j = 0; j < MAX; j++) { if (edges[i][j]) { if (pos[j] == -1) dis++; else if (cur - pos[j] >= k) { flag = 0; break; } else cnt = max(cnt, cur - pos[j]); } } if (dis >= k) flag = 0; if (flag) solve(cur+1, cnt); pos[i] = -1; } }}int main(){ while (cin >> raw_data && raw_data[0] != '#') { analysis(); solve(0, 0); put(); }}