這道題在寫之前一定要把題目讀懂，筆者在設計代碼時就對題意產生了錯誤的理解，好在后來這個錯誤被糾正了，
這道題最主要的點就是對解答樹遍歷并且回溯，也就是《演算法競賽入門經典》中所提到的“剪枝”，遞回的主體是生成結點的全排列，而回溯操作簡單來說就是在這個遞回的基礎上添加的一個判斷，
先說生成全排列遞回的操作，生成全排列就是在現有陣列的基礎上對陣列進行新元素的插入，每次插入都會對已有陣列進行遍歷，如果發現新插入的元素在前面的陣列中已經出現過，那么就跳過剩余操作插入下一個元素，遞回的結束條件就是當前陣列的長度與給出陣列的長度相同，
再說回溯操作，程式中添加了一個變數MINB來記錄當前所有排列中最小的帶寬，每當陣列中新添加了一個元素，就計算該元素(結點)與它相鄰的結點的距離，如果此距離超過了最小帶寬，那么就不用再遍歷下去了，直接回溯，
需要提到的是，程式中圖是使用鄰接矩陣存盤的，不過在把代碼寫完后，筆者發現或許使用鄰接表存盤會更加方便，
1 #include <bits/stdc++.h>
2
3 using namespace std;
4
5 /****************
6 UVa140(帶寬)
7 ***************/
8
9 const int MAX = 8;
10
11 int node[MAX];
12 //用來記錄帶寬最小的結點序列
13 int minB[MAX];
14 //鄰接矩陣
15 int buf[MAX][MAX];
16 int MAXL = 0;//帶寬
17 int MINB = 99999;//最小帶寬
18
19 //該函式是求排列的帶寬的
20 //n:結點個數(字符陣列長度)
21 //cur:當前位置
22 int BandWidth(int n){
23 int cur = 0, i = 0, bnw = 0,j;
24 while(i < n && cur < n){
25 int k = node[cur];
26 //尋找相鄰結點
27 if(buf[k][i]){
28 for(j = 0; j < n; j++){
29 //在結點序列中尋找相鄰結點
30 if(node[j] == i){
31 bnw = max(abs(j-cur), bnw);
32 }
33 }
34 }
35 //某個結點遍歷結束
36 if(i == n-1){
37 i = 0;
38 cur++;
39 continue;
40 }
41 i++;
42 }
43 return bnw;
44 }
45
46 void solve(int n, int cur)
47 {
48 if(cur == n){
49 MAXL = BandWidth(n);
50 if(MINB > MAXL){
51 for(int i = 0; i < n; i++){
52 minB[i] = node[i];
53 }
54 MINB = MAXL;
55 }
56 }
57 else{
58 for(int i = 0; i < n; i++){
59 int ok = 1;
60 for(int j = 0; j < cur; j++)
61 if(node[j] == i) ok = 0;
62 if(ok){
63 int tmp = 0;
64 //尋找相鄰結點
65 for(int j = 0; j < n; j++){
66 if(buf[i][j]){
67 //遍歷當前陣列有沒有相鄰結點
68 for(int k = 0; k < cur; k++)
69 if(node[k] == j)
70 tmp = MINB - (cur - k);
71 }
72 if(tmp < 0) return;
73 }
74 node[cur] = i;
75 solve(n, cur+1);
76 }
77 }
78 }
79
80 }
81
82 int main()
83 {
84 //n:結點數
85 int n = 0;
86 cin >> n;
87 //x,y是邊的兩條結點
88 char x, y;
89 memset(buf, 0, sizeof(buf));
90 //構建鄰接矩陣
91 while(true){
92 cin >> x;
93 cin >> y;
94 if(x == '#' && y == '#') break;
95 buf[x-65][y-65] = 1;
96 buf[y-65][x-65] = 1;
97 }
98 solve(n, 0);
99 //輸出結果
100 for(int i = 0; i < n; i++){
101 printf("%c", minB[i]+65);
102 }
103 printf("\n");
104 printf("%d", MINB);
105 return 0;
106 }
在撰寫代碼時覺得代碼還不夠精簡，或許還有優化空間，
運行結果為：
8
A B
A F
B C
B G
C D
D E
D G
E H
F G
F H
# #
ABCFGDHE
3
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/3881.html
標籤：其他
上一篇：陣列墻 最詳細的解題報告