首页 > 代码库 > Uva140 Bandwidth 全排列+生成测试法+剪枝
Uva140 Bandwidth 全排列+生成测试法+剪枝
参考过仰望高端玩家的小清新的代码。。。
思路:1.按字典序对输入的字符串抽取字符,id[字母]=编号,id[编号]=字母,形成双射
2.邻接表用两个vector存储,存储相邻关系
3.先尝试字母编号字典序最小的排列,此为next_permutation的最上排列
4.在最理想的情况下都不能得到比当前最优解更好的方案,则应当剪枝(prune)
5.memcpy(),strchr()方法来自于库函数
测试集:
Input:
A:FB;B:GC;D:GC;F:AGH;E:HD;
#
Oput:
A B C F G D H E -> 3
1 //id[]输入字母的编号 2 //p[i]排列的字母编号 do{}先执行最小字典序的排列 3 4 5 #include<cstdio> 6 #include<cstring> 7 #include<vector> 8 #include<algorithm> 9 using namespace std; 10 11 const int maxn=10,inf=0x7fffffff; 12 char letter[maxn], s[100];//字母,输入序列 13 int id[256]; //字母的编号 14 int p[maxn]; //全排列的遍历数组 ,存储的是每个字母的编号 15 int pos[maxn];//记录每个字母的位置,避免频繁使用strchr 16 17 int main(){ 18 while(scanf(" %s",&s),s[0]!=‘#‘){ 19 int len=strlen(s),n=0; 20 for(char ch=‘A‘;ch<=‘Z‘;ch++)if(strchr(s,ch)!=NULL){ 21 letter[n]=ch; 22 id[ch]=n++; 23 } 24 vector<int> u,v; 25 for(int i=0;i<len;i++){ 26 int t=i;//记录起始节点 27 i+=2; 28 while(i<len && s[i]!=‘;‘){ 29 u.push_back(id[s[t]]);//加入起始节点 30 v.push_back(id[s[i]]);//加入起始节点的相邻节点 31 i++; 32 } 33 } 34 //遍历+剪枝 35 int bandwidth=0,res=inf; 36 int bestP[maxn];//存储最终结果 37 for(int i=0;i<n;i++)p[i]=i; 38 do{ 39 bandwidth=0;//初始化别忘了 40 for(int i=0;i<n;i++)pos[p[i]]=i;//记录编号为pi的节点的位置 41 for(int i=0;i<u.size();i++){ 42 bandwidth=max(bandwidth,abs(pos[u[i]]-pos[v[i]])); 43 if(bandwidth>=res)break;//剪枝 44 } 45 if(bandwidth<res){ 46 memcpy(bestP,p,sizeof(p));//memcpy比较快 47 res=bandwidth; 48 } 49 }while(next_permutation(p,p+n)); 50 for(int i=0;i<n;i++)printf("%c ",letter[bestP[i]]); 51 printf("-> %d\n",res); 52 } 53 }
Uva140 Bandwidth 全排列+生成测试法+剪枝
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。