当前位置: 代码迷 >> 综合 >> 例题7-6 UVa140 Bandwidth(枚举+剪枝)
  详细解决方案

例题7-6 UVa140 Bandwidth(枚举+剪枝)

热度:67   发布时间:2024-01-16 13:52:49.0

题意:

看白书

要点:

就是全排列问题加上一些剪枝,输入存储有些麻烦。注意如果有多个最小的排列,输出字典序最小的那个


#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
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;
}