給出一個圖節點數為n（n8）讓這些節點排序，使得節點的最大帶寬要最小，最大帶寬就是排列里面與節點相離最遠的距離。

有兩種方法，第一，因為n比較小就可以枚舉全部，然后一個一個的比較，還有一種就是邊排列邊比較。只要其中兩個節點的距離大于目前最大，那么下面的排列可以直接省去。

#include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std;const int maxn = 10; int id[256], letter[maxn]; int P[maxn], bestP[maxn], pos[maxn]; vector<int>u, v; int ans; void dfs(int n,int *A,int cur) {if (cur == n) {for (int i = 0; i < n; i++)pos[A[i]] = i;int bandwidth = 0;for (int i = 0; i < u.size(); i++) {bandwidth = max(bandwidth,abs(pos[u[i]] - pos[v[i]]));}if (ans > bandwidth) {ans = bandwidth;for (int i = 0; i < n; i++)bestP[i] = A[i];}}else for (int i = 0; i < n; i++) {int ok = 1;for (int j = 0; j < cur; j++) {if (A[j] == i)ok = 0;}if (ok) {A[cur] = i;dfs(n,A,cur + 1);}} } int main() {char input[1000];while(scanf("%s", input) == 1 && input[0] != '#') {int n = 0; memset(pos, 0, sizeof(pos));memset(bestP, 0, sizeof(bestP));u.clear(); v.clear();for (char ch = 'A'; ch < 'Z'; ch++) {if (strchr(input, ch) != NULL) {id[ch] = n++;letter[id[ch]] = ch;}}int len = strlen(input), p = 0, q = 0;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.push_back(id[input[p - 1]]);v.push_back(id[input[i]]);}p++; q++;}ans = n; int A[10];dfs(n, A, 0);for (int i = 0; i < n; i++) printf("%c ", letter[bestP[i]]);printf("-> %d\n", ans);}return 0; }

?

下面這種是使用了next_permutation方法

#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[ch] = n++;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.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; }

?

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的UVA140 Bandwidth带宽的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。