本文主要是介绍Bandwidth，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
看吧 你个懒蛋
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int map[26][26] = {};
int app[26] = {}, n;
int set[26] = {}, tmp[26];
int way[26] = {}, used[26] = {};
int ans;
int dfs(int idx) {if(idx == n) {int i, j;int bandwidth = 0;for(i = 0; i < n; i++) {for(j = 0; j < 26; j++) {if(map[app[i]][j]) {if(abs(set[app[i]] - set[j]) > bandwidth)bandwidth = abs(set[app[i]] - set[j]);}}}if(bandwidth < ans) {ans = bandwidth;memcpy(way, tmp, sizeof(way));}return 0;}int i;for(i = 0; i < n; i++) {if(used[i] == 0) {used[i] = 1;tmp[idx] = app[i];set[app[i]] = idx;dfs(idx+1);used[i] = 0;}}
}
int main() {char s[100];int i, j, st, ed;while(scanf("%s", s) == 1) {if(!strcmp(s, "#"))break;memset(map, 0, sizeof(map));int len = strlen(s), used[26] = {};n = 0;for(i = 0; i < len; i++) {st = s[i]-'A';if(used[st] == 0) {used[st] = 1;app[n++] = st;}j = i+2;while(s[j] != ';' && s[j] != '\0') {ed = s[j]-'A';map[st][ed] = 1;if(used[ed] == 0) {used[ed] = 1;app[n++] = ed;}j++;}i = j;}std::sort(app, app+n);ans = 0xffff;dfs(0);for(i = 0; i < n; i++)printf("%c ", way[i]+'A');printf("-> %d\n", ans);}return 0;
}#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;const int maxn = 10;
int id[256], letter[maxn];int main() {char input[1000];while(scanf("%s", input) == 1 && input[0] != '#') {// 计算结点个数并给字母编号int n = 0;for(char ch = 'A'; ch <= 'Z'; ch++)if(strchr(input, ch) != NULL) {// id['A'] = 0 依次类推id[ch] = n++;// letter[0] = 'A' 依次类推letter[id[ch]] = ch;}// 处理输入int len = strlen(input), p = 0, q = 0;vector<int> u, v;for(;;) {while(p < len && input[p] != ':') p++;if(p == len) break;while(q < len && input[q] != ';') q++;for(int i = p+1; i < q; i++) {// u[i]->v[i]为邻接边// 找到顶点u.push_back(id[input[p-1]]);// 找到邻接点v.push_back(id[input[i]]);}p++; q++;}// 枚举全排列int P[maxn], bestP[maxn], pos[maxn], 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 bandwidth = 0;for(int i = 0; i < u.size(); i++)bandwidth = max(bandwidth, abs(pos[u[i]] - pos[v[i]])); // 计算带宽if(bandwidth < ans) {ans = bandwidth;memcpy(bestP, P, sizeof(P));}} while(next_permutation(P, P+n));// 输出for(int i = 0; i < n; i++) printf("%c ", letter[bestP[i]]);printf("-> %d\n", ans);}return 0;
} #include <iostream> #include <cstdio> #include <cstdlib> #include <cctype> #include <cstring> #include <string> #include <sstream> #include <vector> #include <set> #include <map> #include <algorithm> #include <stack> #include <queue> #include <bitset> #include <cassert> #include <cmath> #include <functional> using namespace std; const int maxn = 10; int id[256], letter[maxn]; char input[1000]; int n; void init() // 计算结点的个数并给字母编号 { n = 0; for (char ch = 'A'; ch <= 'Z'; ch++) { if (strchr(input, ch) != NULL) { id[ch] = n++; letter[id[ch]] = ch; } } } // 处理输入 vector <int> u, v; void readInput() { int len = strlen(input); int p = 0, q = 0; u.clear(); v.clear(); while (1) { while (p < len && input[p] != ':') { p++; } if (p == len) { break; } while (q < len && input[q] != ';') { q++; } for (int i = p + 1; i < q; i++) { u.push_back(id[input[p - 1]]); v.push_back(id[input[i]]); } p++; q++; } } // 枚举全排列 void solve() { int P[maxn], bestP[maxn], pos[maxn], 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 bandwidth = 0; for (int i = 0; i < u.size(); i++) { bandwidth = max(bandwidth, abs(pos[u[i]] - pos[v[i]])); // 计算带宽 } if (bandwidth < ans) { ans = bandwidth; memcpy(bestP, P, sizeof(P)); } } while (next_permutation(P, P + n)); // 输出 for (int i = 0; i < n; i++) { cout << (char)letter[bestP[i]] << ' '; } cout << "-> " << ans << endl; } int main() { while (cin >> input && input[0] != '#') { init(); readInput(); solve(); } return 0; } 这篇关于Bandwidth的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
