UVA 140 带宽 Bandwidth （暴力枚举+剪枝）

解题思路：本题使用了STL中的next_permutation()函数（位于algorithm中）列举排列。先记录目前已经找到的最小带宽min_width，如果发现已经有某两个结点的距离大于或等于min_width，再怎么扩展也不可能比当前解更有，故应“剪”掉，即剪枝

#include<cstdio>#include<algorithm>#include<vector>#include<map>#include<cstring> using namespace std;const int maxn=10;int best[maxn]; //储存最优字符序列（不同数字对应不同字母） int p[maxn];    //保存排列 int pos[maxn];  //字母在序列中的位置 char letter[maxn]; //保存字母结点 map<char,int>map1; //通过字母映射编号（以后编号就代表该字母） vector<int>v,u;    //分别储存起始结点，和起始结点的相邻结点 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); //由于题目要求当解有多个时，输出字典序最小，故需排序 	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]]);//加入起始结点（相邻结点有多少个就要加多少次） 		 	u.push_back(map1[str[i]]);//加入起始结点的相邻结点 		 	i++;		 }	}		int min_width=maxn;   //最小带宽 	for(int i=0;i<count;i++)p[i]=i;   	do{		int nodewidth=0;   //当前序列最大带宽 		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();          //一定要清除容器（当时忘记了错了几次） 	v.clear();	u.clear();	}	return 0;}