首页 > 代码库 > UVa140 Bandwidth (枚举排列)

UVa140 Bandwidth (枚举排列)

2024-08-11 23:40:30   219人阅读

链接：http://acm.hust.edu.cn/vjudge/problem/19399
分析：将结点字母用数字0~n-1表示，id[ch]将字符映射到对应的数字编号，letter将数字编号映射到对应的字符，用两个vector将每个结点的相邻结点编号存下来，然后枚举0~n-1位置上的结点编号，用pos记录每个结点编号所在的位置方便以后查找，然后就是遍历vector，第一个vector代表结点编号i，第二个vector代表结点i的相邻结点编号，找出最远距离，如果当前找到的最远距离已经大于或等于ans，则不能更优应剪枝，然后就是更新ans和bestP，直至枚举完0~n-1的所有排列。

 1 #include <cstring> 2 #include <cstdio> 3 #include <vector> 4 #include <iostream> 5 #include <algorithm> 6 using namespace std; 7  8 const int maxn = 10; 9 int id[256], letter[maxn];10 11 int main() {12     char input[1000];13     while (scanf("%s", input) == 1 && input[0] != ‘#‘) {14         int n = 0;15         for (char ch = ‘A‘; ch <= ‘Z‘; ch++)16             if (strchr(input, ch) != NULL) {17                 id[ch] = n++;18                 letter[id[ch]] = ch;19             }20         vector<int> u, v;21         int len = strlen(input);22         for (int p = 0, q = 0; q < len; p++, q++) {23             while (input[p] != ‘:‘) p++;24             while (q < len && input[q] != ‘;‘) q++;25             for (int i = p + 1; i < q; i++) {26                 u.push_back(id[input[p - 1]]);27                 v.push_back(id[input[i]]);28             }29         }30         int pos[maxn], P[maxn], bestP[maxn], ans = n;31         for (int i = 0; i < n; i++) P[i] = i;32         do {33             for (int i = 0; i < n; i++) pos[P[i]] = i;34             int bandwidth = 0;35             for (int i = 0; i < u.size(); i++) {36                 bandwidth = max(bandwidth, abs(pos[u[i]] - pos[v[i]]));37                 if (bandwidth >= ans) break;38             }39             if (bandwidth < ans) {40                 ans = bandwidth;41                 memcpy(bestP, P, sizeof(P));42             }43         } while (next_permutation(P, P + n));44         for (int i = 0; i < n; i++) printf("%c ", letter[bestP[i]]);45         printf("-> %d\n", ans);46     }47     return 0;48 }

 

UVa140 Bandwidth (枚举排列)


联系
我们