解題思路：本題使用了STL中的next_permutation()函數(shù)（位于algorithm中）列舉排列。先記錄目前已經(jīng)找到的最小帶寬min_width，如果發(fā)現(xiàn)已經(jīng)有某兩個結(jié)點的距離大于或等于min_width，再怎么擴(kuò)展也不可能比當(dāng)前解更有，故應(yīng)“剪”掉，即剪枝

#include<cstdio>#include<algorithm>#include<vector>#include<map>#include<cstring> using namespace std;const int maxn=10;int best[maxn]; //儲存最優(yōu)字符序列（不同數(shù)字對應(yīng)不同字母） int p[maxn];    //保存排列 int pos[maxn];  //字母在序列中的位置 char letter[maxn]; //保存字母結(jié)點 map<char,int>map1; //通過字母映射編號（以后編號就代表該字母） vector<int>v,u;    //分別儲存起始結(jié)點，和起始結(jié)點的相鄰結(jié)點 int main(){	char str[100];	while(scanf("%s",str)==1 && str[0]!='#'){		int len=strlen(str);		int count=0;	for(int i=0;i<len;i++){		if(str[i]>='A'&&str[i]<='Z'){			if(!map1.count(str[i]))			{			letter[count]=str[i];			map1[str[i]]=count++;			}		}	}	sort(letter,letter+count); //由于題目要求當(dāng)解有多個時，輸出字典序最小，故需排序 	for(int i=0;i<count;i++)	map1[letter[i]]=i;  //排序后需重新對不同字母分配編號 	for(int i=0;i<len;i++){		int t=i;		i+=2;		 while(str[i]!=';' && i<len){		 	v.push_back(map1[str[t]]);//加入起始結(jié)點（相鄰結(jié)點有多少個就要加多少次） 		 	u.push_back(map1[str[i]]);//加入起始結(jié)點的相鄰結(jié)點 		 	i++;		 }	}		int min_width=maxn;   //最小帶寬 	for(int i=0;i<count;i++)p[i]=i;   	do{		int nodewidth=0;   //當(dāng)前序列最大帶寬 		for(int i=0;i<count;i++)pos[p[i]]=i;  //各字母在序列中的位置 		for(int i=0;i<v.size();i++)		{		nodewidth=max(nodewidth,abs(pos[v[i]]-pos[u[i]]));	    if(nodewidth>=min_width)break; //剪枝 	   }	   if(min_width>nodewidth){	   	memcpy(best,p,sizeof(p));  //memcpy更快 	   	min_width=nodewidth;	   }	}while(next_permutation(p,p+count));		for(int i=0;i<count;i++)PRintf("%c ",letter[best[i]]);	printf("-> %d/n",min_width);	map1.clear();          //一定要清除容器（當(dāng)時忘記了錯了幾次） 	v.clear();	u.clear();	}	return 0;}