一、题目描述
有一个图，顶点数不超过 8 ，顶点的编号仅由大写字母 A 到 Z 组成。对这些顶点的排序是任意的。定义一个顶点 v 的带宽是与 v 相邻的顶点在顶点序列中与点 v 的最长距离。一个序列的带宽是这些距离的最大值。举例：
图一中，点 A B C D E H F G 的带宽分别是 6, 6, 1, 4, 1, 1, 6, 6 ；图二中，点 A B C D G F H E 的带宽分别是 5, 3, 1, 4, 3, 5, 1, 4 。
输入包含若干个图，每个图占一行，每行有若干个组冒号隔开的顶点和邻接点，每组之间用分号相隔。例：
A:FB;B:GC;D:GC;F:AGH;E:HD
当输入一个 # 时，输入结束。
对每个图，输出具有最小序列带宽的序列和该最小带宽，用 -> 隔开。如果有多个解，输出字典序最小的。对上面的样例，输出为：
A B C F G D H E -> 3
二、算法分析说明与代码编写指导
题目没有对排列加以限制，所有排列都是合法的。如果一张图有 8 个顶点，那么排列就有 8! = 40320 个，每个排列都需要去找出最大带宽。如果输入包含大量的图，总操作数就会非常大，有超时的风险。因此，需要添加条件来进行剪枝。
我们知道，按照定义，一个顶点 v 的带宽是与 v 相邻的顶点在顶点序列中与点 v 的最长距离。一个序列的带宽是这些距离的最大值。那么，用一个变量 bw 记录当前排列已经验证过的点的带宽，bwmin 代表已经找到的最小带宽。如果在验证过程中 bw >= bwmin ，显然这个排列取到的带宽一定会大于 bwmin ，不可能是要求的最优解。那么我们可以直接放弃对这个排列继续验证。
通过 next_permutation 可以获得下一个排列（头文件 algorithm），当一个序列已经达到最大排列，再调用此函数，就会重新回到最小排列，并返回 false ，代表本次重排已经无法将排列变为更大的字典序。
用 bitset<26> g[26] 存储一个邻接矩阵代表一个图的每条边。bitset<26> a 代表 26 个大写字母在图中出现的情况。c[9] 为顶点序列，当找到更小的解时，将这个序列抄送给 d[9] ，以备输出。字母 A 的 ASCII 码是 65 ，存储和演算时我们用 0 ~ 25 分别代表 A 到 Z 。输出的时候，所有的值要加回 65 再打印到屏幕上。algorithm 中的 find 函数可以以线性的复杂度来查找无序序列中的值。当在序列中找到两个邻接点并计算了距离以后，将这个计算结果取绝对值才能最终求得一点的带宽，否则会出现负数，不符合要求。
三、AC 代码（0 ms）
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<bitset>
using namespace std;
#pragma warning(disable:4996)
bitset<26> g[26], a; char t, u, v, c[9], d[9], * ptr, bwmin, bw, p, exitfor;
int main() {
for (;;) {
a.reset(); fill(c, c + 8, 0); bwmin = 127; p = 0; exitfor = 0;
for (unsigned char i = 0; i < 26; ++i)g[i].reset();
for (;;) {
t = getchar();
if (t == '#')return 0;
else if (t == ':') {
for (;;) {
v = getchar();
if (v == ';') { exitfor = 1; break; }
else if (v == '\n') { exitfor = 2; break; }
else { v -= 65; g[u][v] = true, g[v][u] = true; a[v] = true; }
}
if (exitfor == 2)break;
}
else { u = t - 65; a[u] = true; }
}
for (unsigned char i = 0; i < 26; ++i)if (a[i] == true) { c[p] = i; ++p; }
for (;;) {
bw = 0; exitfor = 0;
for (unsigned char i = 0; i < p; ++i) {
for (unsigned char j = 0; j < 26; ++j) {
if (g[c[i]][j] == 1) {
ptr = find(c, c + p, j); bw = max(bw, (char)abs(ptr - c - i)); if (bw >= bwmin) { exitfor = 1; break; }
}
}
if (exitfor == 1)break;
}
if (bwmin > bw) { bwmin = bw; for (unsigned char i = 0; i < p; ++i)d[i] = c[i]; }
if (next_permutation(c, c + p) == 0)break;
}
for (unsigned char i = 0; i < p; ++i)printf("%c ", d[i] + 65);
printf("-> %hhd\n", bwmin);
}
}