原题链接：https://vjudge.net/problem/UVA-140 分类：回溯法 备注：最优剪枝
在排序的过程中判断目前的最大带宽，如果大于已记录的带宽则回溯，只有排序一轮完成后再判断目前的宽带和已经记录的带宽，若更小则更新排序数组和带宽值，否则直接返回。此外根据紫书思路，还能利用u节点有m个相邻节点没有确定位置，则若m>k也可回溯。如果加上这一剪枝，运行能从30-40(ms)直接变为0(ms)。代码如下：
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<string> #include<vector> #include<cmath> #include<map> using namespace std; const int inf = 0x3f3f3f3f; string line; vector<char>hav; map<char,vector<char> >link; map<char, int>id, set; //id记录每个元素在vis数组中的下标(方便判断是否已用),//set记录在now数组中的下标(用于计算距离) char out[26], now[26]; int ans; int find(int pos) { int ret = 0; char x = now[pos]; int len2 = link[x].size(); for (int j = 0; j < len2; j++) { if (set[link[x][j]] < 0)continue; ret = max(ret, abs(set[x] - set[link[x][j]])); }//找出对应的最大值,若没有则返回inf return ret; } bool check(int pos) { char x = now[pos]; int m = 0; for (int i = 0; i < link[x].size(); i++) if (set[link[x][i]] < 0)m++; if (m > ans)return false; return true; } void solve(int pos,int tmp) { if (pos == hav.size()) { if (ans == tmp)return; ans = tmp; for (int i = 0; i < pos; i++) out[i] = now[i]; return; } for (int i = 0; i < hav.size(); i++) { if (set[hav[i]] >= 0)continue; now[pos] = hav[i]; set[hav[i]] = pos; tmp = max(tmp, find(pos)); if (tmp > ans || !check(pos)) { set[hav[i]] = -1; continue; } solve(pos + 1, tmp); set[hav[i]] = -1; } } int main(void) { while (cin >> line) { if (line == "#")break; ans = inf; id.clear(); hav.clear(); for (char i = 'A'; i <= 'Z'; i++) { link[i].clear(); set[i] = -1; } int bef = -1, pos = 0; for (int i = 0; i < 26; i++) link[i].clear(); for (int i = 0; i < line.length(); i++) //记录已有元素 if (isalpha(line[i])) { if (id.count(line[i]))continue; id[line[i]] = hav.size(); hav.push_back(line[i]); } sort(hav.begin(), hav.end()); for (int i = 0; i < hav.size(); i++) id[hav[i]] = i; while (pos < line.length()) {//记录相邻元素 while (pos < line.length() && line[pos] != ';')pos++; char x = line[bef + 1]; for (int i = bef + 3; i < pos; i++) { link[x].push_back(line[i]); bool flag = false; for (int j = 0; j < link[line[i]].size(); j++) { if (link[line[i]][j] == x) { flag = true; break; } } if (!flag)link[line[i]].push_back(x); } bef = pos; pos++; } solve(0, 0); for (int i = 0; i < hav.size(); i++) printf("%c ", out[i]); printf("-> %d\n", ans); } return 0; }