题意：
看白书
要点：
就是全排列问题加上一些剪枝，输入存储有些麻烦。注意如果有多个最小的排列，输出字典序最小的那个
#include#include #include #include #include #include using namespace std;int num, ahl[30], map[30][30];int save[10], node[10];char a[500];int main(){ int len, max,c; while (scanf("%s",a)!=EOF) { if (!strcmp(a, "#")) break; max = 10;num = 0; int flag = 0; len = strlen(a); memset(ahl, 0, sizeof(ahl)); memset(map, 0, sizeof(map)); for (int i = 0; i < len; i++) { if (isalpha(a[i])) ahl[a[i] - 'A'] = 1; if (a[i] == ':') { c = a[i-1] - 'A';//这里是i-1，第一次错在这里调试半天 flag = 1; } else if (flag&&isalpha(a[i])) map[c][a[i] - 'A'] = map[a[i] - 'A'][c] = 1;//存储邻接的点 else if (a[i] == ';') flag = 0; } for (int i = 0; i < 26; i++)//按照字母表排序，已经字典序最小 if (ahl[i]) node[num++] = i; do { int ans = 0;; for (int i = 0; i < num; i++) { for (int j = i+1; j < num; j++) { if (map[node[i]][node[j]]) if (abs(i - j)>ans) ans = abs(i - j);//取当前排列的最大值 } if (ans > max)//剪枝，如果当前算出的值已经大于max，说明这种排列肯定不是最小的那种 break; } if (ans < max) { max = ans; memcpy(save, node, sizeof(node)); } } while (next_permutation(node, node + num));//直接用下一个排列，因为一开始是最小的所以保证了输出字典序最小的 for (int i = 0; i < num; i++) printf("%c ", save[i] + 'A'); printf("-> %d\n",max); } return 0;}