【题意】给定一个图(V,E),其中V为顶点的集合,E为边的集合,属于VxV。给定V中元素的一种排序,那么顶点v的带宽定义如下:在当前给定的排序中,与v距离最远的且与v有边相连的顶点与v的距离。给定排序的带宽定义为各顶点带宽的最大值,这个题的题意要花点时间理解,具体可以看紫书 P 196,上面有图,可以更好理解。
【解题方法】
本题有如下关键点:
1 建立双射关系:从字符A到字符Z遍历输入的字符串,用strchr函数将输入中出现的字符找出,并将找出的字符进行编号,用letter和id分别存储字符和对应的编号
2 降维:输入中给出的,是类似于邻接表形式的二维形式,如果我们用二维数据结构,将增加处理时对于输出细节的处理难度,用 2个 vector将输出降低到1维,简化了计算Bandwidth时的代码,实际上让我们更加有的放矢
3 存储必要信息——位置:数组pos每个下标代表字母编号,存储的是对应的位置下标,便于计算时寻找位置。
4 剪枝:减去不必要的计算(虽然对于本题而言不是必须的)
5 库函数的使用:memcpy,strchr,strlen,next_permutation的使用简化了代码,突出了逻辑部分。
【AC代码】
其中注释掉的是直接暴力枚举,超时的代码。
//
//Created by just_sort 2016/1/5
//Copyright (c) 2016 just_sort.All Rights Reserved
//
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/hash_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <time.h>
#include <cstdlib>
#include <cstring>
#include <sstream> //isstringstream
#include <iostream>
#include <algorithm>
using namespace std;
//using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int, LL> pp;
#define REP1(i, a, b) for(int i = a; i < b; i++)
#define REP2(i, a, b) for(int i = a; i <= b; i++)
#define REP3(i, a, b) for(int i = a; i >= b; i--)
#define CLR(a, b) memset(a, b, sizeof(a))
#define MP(x, y) make_pair(x,y)
const int maxn = 1e3 + 10;
const int maxm = 2e5;
const int maxs = 10;
const int maxp = 1e3 + 10;
//const int INF = 1e9;
const int UNF = -1e9;
const int mod = 1e9 + 7;
int gcd(int x, int y) {return y == 0 ? x : gcd(y, x % y);}
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>order_set;
//head
//char s[110];
//char a[10];
//map <pair <char, char>, int> mp;
//
//int main()
//{
// while(scanf("%s", s) != EOF)
// {
// mp.clear();
// if(s[0] == '#') break;
// int len = strlen(s);
// int cnt = 0;
// memset(a, '0', sizeof(a));
// REP1(i, 0, len){
// //a[cnt++] = s[i];
// if(!isalpha(s[i])) continue;
// bool equ = 0;
// for(int j = 0; j < cnt; j++){
// if(a[j] == s[i]) equ = 1;
// }
// if(!equ) a[cnt++] = s[i];
// }
// for(int i = 0; i < cnt; i++){
// printf("%c ", a[i]);
// }
// printf("\n");
// char x;
// bool ok = 0;
// REP1(i, 0, len){
// if(isalpha(s[i]) && !ok) continue;
// if(s[i] == ':') x = s[i - 1], ok = 1;
// else if(isalpha(s[i]) && ok){
// mp[MP(x, s[i])] = 1;
// mp[MP(x, s[i])] = 1;
// }
// else if(s[i] == ';'){
// ok = 0;
// }
// }
// //clock_t st = clock();
// int ans = 1e9;
// do{
// int maxx = 0;
// REP1(i, 0, len){
// int mx = 0;
// REP1(j, 0, len){
// if(j == i) continue;
// if(mp[MP(a[i], a[j])]){
// mx = max(mx, abs(i - j));
// }
// }
// maxx = max(maxx, mx);
// }
// ans = min(ans, maxx);
// }while(next_permutation(a, a + cnt));
//// clock_t en = clock();
//// cout << (en - st) / CLK_TCK << endl;
// }
// return 0;
//}
int id[110], letter[10];
char s[1010];
int main()
{
while(scanf("%s", s) != EOF)
{
if(s[0] == '#') break;
int n = 0;
for(char ch = 'A'; ch <= 'Z'; ch++){
if(strchr(s, ch) != NULL){
id[ch] = n++;
letter[id[ch]] = ch;
}
}
vector <int> u, v;
int len = strlen(s);
int p = 0, q = 0;
while(1){
while(p < len && s[p] != ':') p++;
if(p == len) break;
while(q < len && s[q] != ';') q++;
for(int i = p + 1; i < q; i++){
u.push_back(id[s[p - 1]]);
v.push_back(id[s[i]]);
}
p++, q++;
}
int P[10], bestP[10], pos[10], ans = n;
for(int i = 0; i < n; i++) P[i] = i;
do{
for(int i = 0; i < n; i++) pos[P[i]] = i;
int daikuan = 0;
for(int i = 0; i < u.size(); i++){
daikuan = max(daikuan, abs(pos[u[i]] - pos[v[i]]));
}
if(daikuan < ans){
ans = daikuan;
memcpy(bestP, P, sizeof(bestP));
}
}while(next_permutation(P, P + n));
for(int i = 0; i < n; i++) printf("%c ", letter[bestP[i]]);
printf("-> %d\n", ans);
}
return 0;
}