题目大意：给出一些点，点和点之间是否相连，求这些点怎么排列可以使的所有点形成的图的带宽最小。如果有多种情况按照字典序输出。图的带宽指的是点的带宽的最大值，点的带宽指的是，所有和这个点联通的其他的点到这个点的距离的最大值。
解题思路：转换成全排列问题。将这里点和点的联通关系存放在邻接表中，注意这里的边是无向的就说明点和点之间的连通关系是双向的。然后对全排列进行筛选。如果某个点与他相邻的点的距离>= 现在所暂定的最小值，就说明这种状况下无法产生比原来的状况更好的排列，就不需要扩展了。还有如果这个点还有m个相邻的点未确定位置，这样的最好情况就是这m个点都排在这个点的后面，最好的情况带宽是m，如果m>=当前暂定的最小值，这就说明最好情况下都不可能产生比原理的状况更好的序列，这样的情况就可以不用往后面扩展了。还有全排列的时候要按照字典序先的来排，这样在带宽相同的情况下就只要比较前面的排列即可。
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stdlib.h>
using namespace std;
const int N = 8;
const int M = 26;
char e[M][M];
char str[N * M], s[N], c[N], co[N];
int n, vis[M], sum;
void handle (int cur) {
if (cur == n) {
int count1 = 0;
for (int i = 0; i < cur; i++) {
int count = 0;
for (int j = 0; j < M; j++) {
if (e[c[i] - ‘A‘][j])
for (int k = 0; k < cur; k++)
if (c[k] == j + ‘A‘ && count < abs(i - k)) {
count = abs(i - k);
break;
}
}
if (count1 < count)
count1 = count;
}
if (count1 < sum) {
sum = count1;
for (int i = 0; i < cur; i++)
co[i] = c[i];
}
return;
}
for (int i = 0; i < n; i++) {
if (!vis[s[i] - ‘A‘]) {
bool flag = 1; int count = 0;
for (int j = 0; j < M; j++) {
if (e[s[i] - ‘A‘][j]) {
int count1 = 0;
for (int k = 0 ; k < cur; k++) {
if ( c[k] == j + ‘A‘ && abs(k - cur) >= sum) flag = 0;
if (!flag)
break;
if ( c[k] != j + ‘A‘)
count1++;
}
if (!flag)
break;
if (count1 == cur)
count++;
}
}
if (flag && count >= sum )
flag = 0;
if (flag) {
c[cur] = s[i];
vis[s[i] - ‘A‘] = 1;
handle(cur + 1);
vis[s[i] - ‘A‘] = 0;
}
}
}
}
int main () {
while (scanf("%s", str) && str[0] != ‘#‘) {
char *p = str;
memset(e, 0, sizeof(e));
memset(vis, 0, sizeof(vis));
n = 0;
for (; *p;) {
if (*p >= ‘A‘ && *p <= ‘Z‘ && ( *(p + 1) == ‘:‘ || !*(p + 1))) {
int n1 = *p - ‘A‘, t = 0;
if (!vis[*p - ‘A‘]) {
s[n++] = *p;
vis[*p - ‘A‘] = 1;
}
if (!*( p + 1))
break;
for (p = p + 2; *p != ‘;‘ && *p; p++) {
e[n1][*p - ‘A‘] = 1;
e[*p - ‘A‘][n1] = 1;
if (!vis[*p - ‘A‘]) {
s[n++] = *p;
vis[*p - ‘A‘] = 1;
}
}
if (*p == ‘;‘)
p++;
}
}
memset(vis, 0, sizeof(vis));
sort(s, s + n);
sum = N;
handle(0);
for (int i = 0; i < n; i++)
printf("%c ", co[i]);
printf("-> %d\n", sum);
}
return 0;
}140 - Bandwidth（排列（带宽问题））,布布扣,bubuko.com
原文：http://blog.csdn.net/u012997373/article/details/23017849