学步园

这题理解起来也需要一点时间，其实也是一个枚举排列，只不过这次的限制条件没了，但引入了优化条件：让整个排列的带宽最小。

最简单的做法：

记录一共有多少个字母，然后枚举全排列。对于每个排列，算出带宽，找出最小的排列

改进：

因为没有了限制条件（比如八皇后中的不能相互攻击、例题7-5中的“困难”），解答树似乎需要完全遍历。

但是因为目标要求出最小值，所以任何带宽比当前已经达到的最小值大的中间产物都可以抛弃不要（剪枝）。

（书中还有一条剪枝原则：如果刚刚填进去的元素还有m个相邻元素没有被用到，那么再往后填，最好的情况就是这m个元素依次排在后面。这样到最后的带宽至少是当前带宽+m。所以如果当前贷款+m大于目前已达到的最小值，则可以剪枝）

一个小细节：

不能像前面7-5一样用一个L来代表取值集合了，要把出现过的字母存下来，每次枚举这个集合，而不能简单地从0枚举到L-1了。

Run Time: 0.235s

#define UVa  "LT7-6.140.cpp"

#include<cstring>
#include<cstdlib>
#include<cstdio>

#include<string>
#include<vector>
#include<set>

#define maxn 500

using namespace std;


//Global Variables.
char line[maxn];
set<int> vertice;
vector<int> edges[30];
vector<int> result;
int sequence[10];
int min_bandwidth;
/////

void print_result(int bandwidth) {
    for(int i = 0; i < result.size(); i ++)
        printf("%c ", result[i]+'A');
    printf("-> %d\n", bandwidth);
}

void read_graph() {
    int vert1 = -1;
    for(int i = 0; i < strlen(line); i ++) {
        if(line[i] == ';') {
            vert1 = -1;
            continue;
        }
        if(isalpha(line[i])) {
            if(vert1 == -1) {
                vert1 = line[i] - 'A';
                vertice.insert(vert1);
            }
            else {
                int vert2 = line[i] - 'A';
                edges[vert1].push_back(vert2);
                vertice.insert(vert2);
            }
        }
    }
}

int get_bandwidth(int cur) {
    int pos1 = 0, pos2 = 0, maxbandwidth = 0, i, j;
    for(i = 0; i < 30; i ++) {
        if(edges[i].size())
            for(j = 0; j < cur; j ++)
                if(sequence[j] == i) {
                    pos1 = j;
                    break;
                }

        if(j == cur) continue;  //Not found in current sequence.

        for(int j = 0; j < edges[i].size(); j ++)
            for(int k = 0; k < cur; k ++)
                if(sequence[k] == edges[i][j]) {        //Locate the vertices.
                    pos2 = k;
                    maxbandwidth = max(maxbandwidth, abs(pos2 - pos1));
                    break;
                }
    }
    return maxbandwidth;
}

int solve(int cur) {
    if(cur == vertice.size()) {
        int cur_bandwidth = get_bandwidth(cur);
        if(!min_bandwidth || cur_bandwidth < min_bandwidth) {
            result.clear();
            for(int i = 0; i < cur; i ++) result.push_back(sequence[i]);
            min_bandwidth = cur_bandwidth;
        }
        else if(cur_bandwidth == min_bandwidth) {           //lexicographic ordering
            int ok = 1;
            for(int i = 0; i < cur; i ++) if(sequence[i] > result[i]) { ok = 0; break; }
            if(ok) {
                result.clear();
                for(int i = 0; i < cur; i ++) result.push_back(sequence[i]);
            }
        }
    }
    else for(set<int>::iterator it = vertice.begin(); it != vertice.end(); it ++) {
        int ok = 1;
        for(int i = 0; i < cur; i ++) if(sequence[i] == *it) { ok = 0; break; }
        if(!ok) continue;
        if(min_bandwidth && get_bandwidth(cur) > min_bandwidth) continue;

        sequence[cur] = (*it);
        solve(cur+1);
    }
}

int main() {
    while(fgets(line,maxn,stdin) && line[0] != '#') {
        vertice.clear();
        result.clear();
        for(int i = 0; i < 30; i ++) edges[i].clear();
        min_bandwidth = 0;
        memset(sequence, -1, sizeof(sequence));

        read_graph();
        solve(0);
        print_result(min_bandwidth);
    }
    return 0;
}