【题意】给定一个图(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;
}