首页 > 代码库 > UVa140 Bandwidth 小剪枝+双射小技巧+枚举全排列+字符串的小处理

UVa140 Bandwidth 小剪枝+双射小技巧+枚举全排列+字符串的小处理

给出一个图,找出其中的最小带宽的排列。具体要求见传送门:UVa140

这题有些小技巧可以简化代码的编写。

本题的实现参考了刘汝佳老师的源码,的确给了我许多启发,感谢刘老师。

思路:

  1. 建立双射关系:从字符A到字符Z遍历输入的字符串,用strchr函数将输入中出现的字符找出,并将找出的字符进行编号,用letter和id分别存储字符和对应的编号
  2. 降维:输入中给出的,是类似于邻接表形式的二维形式,如果我们用二维数据结构,将增加处理时对于输出细节的处理难度,用 2个 vector将输出降低到1维,简化了计算Bandwidth时的代码,实际上让我们更加有的放矢
  3. 存储必要信息——位置:数组pos每个下标代表字母编号,存储的是对应的位置下标,便于计算时寻找位置。
  4. 剪枝:减去不必要的计算(虽然对于本题而言不是必须的)
  5. 库函数的使用:memcpy,strchr,strlen,next_permutation的使用简化了代码,突出了逻辑部分。

代码实现如下:

 1 #include<cstdio> 2 #include<cstring> 3 #include<vector> 4 #include<algorithm>  5 using namespace std; 6  7 const int maxn=10,inf=0x7fffffff; 8 char letter[maxn], s[100];//字母,输入序列  9 int id[256]; //字母的编号 10 int p[maxn]; //全排列的遍历数组 ,存储的是每个字母的编号 11 int pos[maxn];//记录每个字母的位置,避免频繁使用strchr 12 13 int main(){14     while(scanf(" %s",&s),s[0]!=#){15         int len=strlen(s),n=0;16         for(char ch=A;ch<=Z;ch++)if(strchr(s,ch)!=NULL){17             letter[n]=ch;18             id[ch]=n++;19         }20         vector<int> u,v;21         for(int i=0;i<len;i++){22             int t=i;//记录起始节点 23             i+=2;24             while(i<len && s[i]!=;){25                 u.push_back(id[s[t]]);//加入起始节点 26                 v.push_back(id[s[i]]);//加入起始节点的相邻节点 27                 i++;28             }29         }30         //遍历+剪枝31         int bandwidth=0,res=inf;32         int bestP[maxn];//存储最终结果 33         for(int i=0;i<n;i++)p[i]=i;34         do{35             bandwidth=0;//初始化别忘了 36             for(int i=0;i<n;i++)pos[p[i]]=i;//记录编号为pi的节点的位置 37             for(int i=0;i<u.size();i++){38                 bandwidth=max(bandwidth,abs(pos[u[i]]-pos[v[i]]));39                 if(bandwidth>=res)break;//剪枝40             }41             if(bandwidth<res){42                 memcpy(bestP,p,sizeof(p));//memcpy比较快 43                 res=bandwidth;44             }45         }while(next_permutation(p,p+n));46         for(int i=0;i<n;i++)printf("%c ",letter[bestP[i]]);47         printf("-> %d\n",res);48     }49 }

技术分享

UVa140 Bandwidth 小剪枝+双射小技巧+枚举全排列+字符串的小处理