题目链接：https://vjudge.net/problem/UVA-140
题解：这道题利用全排函数即可解决，但是这道题技巧性强，稍微不注意就会超时，一开始没有想起全排函数，自己写回溯全排超时了，主要问题出在：1、递归过程中疯狂判断最小带宽，循环太多了。2、处理原字符串的方法太LOW了。在借鉴了紫书思路的之后写出了AC代码如下：
AC代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define MAXN 30
using namespace std;
typedef long long ll; vector<int> u;
vector<int> v; int main(void){
char s[];
while(scanf("%s",s) == && s[] != '#'){
u.clear();
v.clear();
int len = strlen(s);
int p = ,q = ;
int n = ;
int id[];
char letter[MAXN];
for(char i = 'A';i<='Z';i++){
if(strchr(s,i) != NULL){
id[i] = n++;
letter[id[i]] = i;
}
}
for(;;){
if(p<len && q < len){
while(){
if(s[p] == ':'){
break;
}
p++;
if(p == len){
break;
}
}
while(){
if(s[q] == ';'){
break;
}
q++;
if(q == len){
break;
}
}
for(int i = p+;i<q;i++){
u.push_back(id[s[p - ]]);
v.push_back(id[s[i]]);
}
}
else
break;
p++;q++;
}
int P[MAXN],BESTP[MAXN];
int pos[MAXN];
int best = n;
for(int i = ;i<n;i++){
P[i] = i;
}
do{
for(int i = ;i<n;i++){
pos[P[i]] = i;
}
int bandwith = ;
for(int i = ;i<u.size();i++){
bandwith = max(bandwith,abs(pos[u[i]]-pos[v[i]]));
}
if(bandwith < best){
best = bandwith;
memcpy(BESTP,P,sizeof(P));
}
}while(next_permutation(P,P+n));
for(int i = ; i < n; i++) printf("%c ", letter[BESTP[i]]);
printf("-> %d\n", best);
}
return ;
}
超时代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<cmath>
#define MAXN 30
using namespace std;
typedef long long ll;
int mmin;
int maxalp;
int nowMin;
int graph[MAXN][MAXN];
int nowbox[MAXN];
int ansbox[MAXN];
void findNiceList(int cur){
if(cur - == maxalp){
int ok = ;
int nowbig;
int big1;
int big = ;
for(int i =;i<cur;i++){
big1 = ;
if(!ok){
break;
}
int nowchar = nowbox[i];
for(int j = ;j<=maxalp;j++){
if(graph[nowchar][j] == ){
nowbig = abs((find(nowbox,nowbox+cur,j) - nowbox) - i);
if(nowbig > big1){
big1 = nowbig;
}
if(big1 >= mmin){
ok = ;
break;
}
}
}
if(big1 > big){
big = big1;
}
}
nowMin = big;
if(nowMin < mmin && ok){
for(int i = ;i<=maxalp;i++){
ansbox[i] = nowbox[i];
mmin = nowMin;
}
}
}
else{
for(int i = ;i<=maxalp;i++){
int ok = ;
for(int j = ;j<cur;j++){
if(nowbox[j] == i){
ok = ;
break;
}
}
if(ok){
nowbox[cur] = i;
findNiceList(cur+);
}
}
}
} /*void graphprint(void){
for(int i = 0;i<=maxalp;i++){
printf("%c:",'A'+i);
for(int j = 0; j<MAXN;j++){
if(graph[i][j] == 1){
printf("%c ",j+'A');
}
}
printf("\n");
}
}*/ int main(void){
string inistr;
const string endstr = "#";
while((cin >> inistr) && inistr != endstr){
memset(graph,-,sizeof(graph));
int len = inistr.size();
maxalp = -;
mmin = ;
nowMin = ;
for(int i = ;i < len;i++){
if(inistr[i] <= 'Z' && inistr[i] >='A'){
if(inistr[i] - 'A' > maxalp){
maxalp = inistr[i] - 'A';
}
}
if(i+ == len || inistr[i+] == ';'){
int okindex;
for(int m = i - ;m>=;m--){
if(inistr[m] == ':'){
okindex = m;
break;
}
}
for(int m = okindex + ;m<=i;m++){
graph[inistr[okindex - ] - 'A'][inistr[m] - 'A'] = ;
graph[inistr[m] - 'A'][inistr[okindex - ] - 'A'] = ;
}
}
}
findNiceList();
for(int i = ;i<=maxalp;i++){
printf("%c ",ansbox[i] + 'A');
}
printf("-> ");
printf("%d\n",mmin);
}
return ;
}