140 - Bandwidth（排列（带宽有关问题））

140 - Bandwidth（排列（带宽问题））

题目：140 - Bandwidth

题目大意：给出一些点，点和点之间是否相连，求这些点怎么排列可以使的所有点形成的图的带宽最小。如果有多种情况按照字典序输出。图的带宽指的是点的带宽的最大值，点的带宽指的是，所有和这个点联通的其他的点到这个点的距离的最大值。

解题思路：转换成全排列问题。将这里点和点的联通关系存放在邻接表中，注意这里的边是无向的就说明点和点之间的连通关系是双向的。然后对全排列进行筛选。如果某个点与他相邻的点的距离>= 现在所暂定的最小值，就说明这种状况下无法产生比原来的状况更好的排列，就不需要扩展了。还有如果这个点还有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;
}