题目链接：https://vjudge.net/problem/UVA-140

题解：这道题利用全排函数即可解决，但是这道题技巧性强，稍微不注意就会超时，一开始没有想起全排函数，自己写回溯全排超时了，主要问题出在：1、递归过程中疯狂判断最小带宽，循环太多了。2、处理原字符串的方法太LOW了。在借鉴了紫书思路的之后写出了AC代码如下：

AC代码：

 

#include
     
      #include
      
       #include
       
        #include
        
         #define MAXN 30using namespace std;typedef long long ll;vector
         
           u;vector
          
            v;int main(void){ char s[1000]; while(scanf("%s",s) == 1 && s[0] != '#'){ u.clear(); v.clear(); int len = strlen(s); int p = 0,q = 0; int n = 0; int id[256]; 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
           
             %d\n", best); } return 0;}
           
          
         
        
       
      
     

 

超时代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define MAXN 30using 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 - 1 == maxalp){ int ok = 1; int nowbig; int big1; int big = 0; for(int i =0;i
           
             big1){ big1 = nowbig; } if(big1 >= mmin){ ok = 0; break; } } } if(big1 > big){ big = big1; } } nowMin = big; if(nowMin < mmin && ok){ for(int i = 0;i<=maxalp;i++){ ansbox[i] = nowbox[i]; mmin = nowMin; } } } else{ for(int i = 0;i<=maxalp;i++){ int ok = 1; for(int j = 0;j
            
             > inistr) && inistr != endstr){ memset(graph,-1,sizeof(graph)); int len = inistr.size(); maxalp = -1; mmin = 99; nowMin = 0; for(int i = 0;i < len;i++){ if(inistr[i] <= 'Z' && inistr[i] >='A'){ if(inistr[i] - 'A' > maxalp){ maxalp = inistr[i] - 'A'; } } if(i+1 == len || inistr[i+1] == ';'){ int okindex; for(int m = i - 1;m>=0;m--){ if(inistr[m] == ':'){ okindex = m; break; } } for(int m = okindex + 1;m<=i;m++){ graph[inistr[okindex - 1] - 'A'][inistr[m] - 'A'] = 1; graph[inistr[m] - 'A'][inistr[okindex - 1] - 'A'] = 1; } } } findNiceList(0); for(int i = 0;i<=maxalp;i++){ printf("%c ",ansbox[i] + 'A'); } printf("-> "); printf("%d\n",mmin); } return 0;}