题目分析问题背景给定一个无向图(V,E)(V, E)(V,E)其中VVV是结点集合EEE是边集合。现要求给出结点的一个排列ordering\texttt{ordering}ordering使得这个排列的“带宽”bandwidth\texttt{bandwidth}bandwidth最小。具体定义如下对于排列中的每个结点vvv其带宽定义为vvv与其所有邻接结点在排列中的位置距离的最大值。整个排列的带宽定义为所有结点带宽的最大值。例如题目图示中给出了两种排列方式带宽分别为666和555目标是找出所有排列中带宽最小的那一个。输入格式输入由多组数据组成每组数据一行以#结束。每组数据由若干个记录组成记录之间用分号分隔。每个记录的格式为结点:邻居1邻居2...结点用单个大写字母A-Z表示图中结点数不超过888个。输出格式对于每组数据输出一行内容为结点1 结点2 ... 结点n - 带宽若有多个排列带宽相同输出字典序最小的那一个。解题思路关键约束结点数≤8\leq 8≤8。带宽定义为排列中任意两个相邻结点之间的最大距离。需要输出字典序最小的最优解。可行解法由于结点数最多为888可以枚举所有可能的排列计算每个排列的带宽并记录最小值。结点数888的全排列共有8!403208! 403208!40320种计算每个排列的带宽是可行的。算法步骤读取一行输入解析出所有结点及其邻接关系。存储结点列表并排序为了后续按字典序生成排列。使用next_permutation枚举所有排列。对于每个排列遍历所有边计算相邻结点在排列中的最大距离即带宽。记录带宽最小的排列若带宽相同则保留字典序更小的。输出结果。时间复杂度枚举排列O(n!)O(n!)O(n!)计算每个排列的带宽O(n2)O(n^2)O(n2)因为需检查所有结点对总复杂度O(n!⋅n2)O(n! \cdot n^2)O(n!⋅n2)在n≤8n \leq 8n≤8时完全可行。代码实现// Bandwidth// UVa ID: 140// Verdict: Accepted// Submission Date: 2016-01-19// UVa Run Time: 0.079s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;string nodes;mapchar,stringneighbours;intgetBandwidth(){intminBandwidth1;for(inti0;inodes.length()-1;i)for(intji1;jnodes.length();j)if(neighbours[nodes[i]].find(nodes[j])!string::npos)if(abs(i-j)minBandwidth)minBandwidthabs(i-j);returnminBandwidth;}voidgetNeighbours(string record){for(inti2;irecord.length();i){neighbours[record[0]]record[i];neighbours[record[i]]record[0];}}intmain(){string line;while(getline(cin,line),line!#){nodes.clear();neighbours.clear();for(inti0;iline.length();i)if(isalpha(line[i])nodes.find(line[i])nodes.npos)nodesline[i];while(line.find(;)!line.npos){getNeighbours(line.substr(0,line.find(;)));lineline.substr(line.find(;)1);}getNeighbours(line);sort(nodes.begin(),nodes.end());intminBandwidth7;string minSequences;minSequences.assign(nodes);do{intbandwidthgetBandwidth();if(bandwidthminBandwidth){minSequences.assign(nodes);minBandwidthbandwidth;}}while(next_permutation(nodes.begin(),nodes.end()));for(inti0;iminSequences.length();i)coutminSequences[i] ;cout- minBandwidth\n;}return0;}总结本题是一个典型的排列枚举 模拟计算问题由于结点数限制很小可以直接使用全排列暴力求解。注意在实现时要处理好输入解析和字典序比较的细节。如果你对图论和排列枚举类问题感兴趣可以进一步学习回溯剪枝和启发式搜索如模拟退火、遗传算法在更大规模问题上的应用。