对于本题，因为数据范围在8！内，我们只需枚举这些字母的全排列就能解决问题，用u和v一起存图，u里为所有边起点，v为终点，枚举全排列，随时更新最值即可。
#include<bits/stdc++.h> using namespace std; int id[256],letter[10]; int main() { int n; char a[10000]; while(scanf("%s",a)==1&&a[0]!=‘#‘) { n=0; for (char ch = ‘A‘; ch <= ‘Z‘; ch++) if (strchr(a, ch) != NULL) {//寻找字符第一次出现的位置。 id[ch] = n++;//记录该字符的编号 letter[id[ch]] = ch;//记录编号几出现的是啥字符 } int len = strlen(a), p = 0, q = 0; vector<int> u, v; for (;;) { while (p < len && a[p] != ‘:‘) p++; if (p == len) break; while (q < len && a[q] != ‘;‘) q++; for (int i = p + 1; i < q; i++) { u.push_back(id[a[p - 1]]);//存储当前位置的起始边 v.push_back(id[a[i]]); } p++; q++; }int P[maxn], bestP[maxn], pos[maxn], ans = n; for (int i = 0; i < n; i++) P[i] = i; do { for (int i = 0; i < n; i++) pos[P[i]] = i; // 每个字母的位置 int bandwidth = 0; for (int i = 0; i < u.size(); i++) bandwidth = max(bandwidth, abs(pos[u[i]] - pos[v[i]])); // 计算带宽 if (bandwidth < ans) { ans = bandwidth; memcpy(bestP, P, sizeof(P)); } } while (next_permutation(P, P + n)); // 输出 for (int i = 0; i < n; i++) printf("%c ", letter[bestP[i]]); printf("-> %d\n", ans); } } return 0; }
如果想提高效率，本题也可以用回溯法完成，用邻接矩阵存图，在全排列额过程中剪枝减少计算量。完成全排列的枚举。时间效率会稍有提高
#include<bits/stdc++.h> using namespace std; const int N=10; int n,id[‘Z‘+1],G[N][N];//为每个字母节点编个号。 int ans,seq[N],tmp[N]; bool used[N]; char u,v,letter[N];//letter[i]记录节点 i 的字母值 inline int dis(int cur,int nid){ for(int i=1;i<cur;i++) if(G[tmp[i]][nid]) return cur-i; return 0; } void dfs(int cur,int bw){ if(cur>n){ ans=bw; memcpy(seq,tmp,sizeof(seq)); return; } //1-n 的全排列 for(int i=1;i<=n;i++) if(!used[i]){ bw=max(bw,dis(cur,i));//计算当前的 bandwidth 值 if(bw<ans){ used[i]=true; tmp[cur]=i; dfs(cur+1,bw); used[i]=false; } } } int main(){ string line,node; char u,v; while(cin>>line&&line!="#"){ n=0,ans=10; memset(G,0,sizeof(G)); memset(id,0,sizeof(id)); memset(used,0,sizeof(used)); for(char i=‘A‘;i<=‘Z‘;i++) if(line.find(i)!=-1){ id[i]=++n; letter[n]=i; } for(int i=0;i<line.size();i++) if(line[i]==‘;‘) line[i]=‘ ‘; stringstream sin(line); while(sin>>node){ node[node.find(‘:‘)]=‘ ‘; stringstream ss(node); ss>>u; while(ss>>v) G[id[u]][id[v]]=G[id[v]][id[u]]=1; } dfs(1,0); for(int i=1;i<=n;i++) cout<<letter[seq[i]]<<‘ ‘; cout<<"-> "<<ans<<endl; } return 0; }
原文：https://www.cnblogs.com/tscjj/p/13769936.html