題意：給出房間寬度r和s個掛墜的重量wi。設(shè)計一個盡量寬（但寬度不能超過房間寬度r）的天平，掛著所有掛墜。天平由一些長度為1的木棍組成。木棍的每一端要么掛一個掛墜，要么掛另一個木棍，設(shè)n和m分別是兩端掛的總重量，要讓天平平衡，必須滿足n*a=m*b。(0<r<10,1s6)。輸出和標準答案的絕對誤差不應(yīng)該超過。

分析：好了數(shù)值很小，可以暴力，問題是怎么枚舉二叉樹。這是本題的難點，很多人第一次做這種類型的題目時，都不知道怎么下手，當然我也是，考慮很久，也寫不出枚舉二叉樹算法，看過解析才知道原來可以這么簡單，才知道自己對二叉樹的理解還是欠缺了。二叉樹的核心在于結(jié)點可以組成節(jié)點。

下面以一個例子來說明：

4個掛墜，每個掛墜重量分別為1，2，3，5。房間寬度為1.7143。

? ? ? ? ? ? ? ? ? ? ? ? 3 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? 0.666|0.333 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ------------------- ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? | ? ? ? ? ? ? ? ? ? ?? | ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1 ? ? ? ? ? ? ? ? ? ? 2

先將第一個節(jié)點和第二個節(jié)點組成一個節(jié)點，重量為3，左邊寬度為0.6666，右邊為0.3333，增加到節(jié)點列表中，節(jié)點列表為1，2，3，5，3。然后繼續(xù)找下一層，找另外兩個沒找過的節(jié)點為3，5，組成節(jié)點，重量為8，增加到節(jié)點列表中，當前節(jié)點列表為1，2，3，5，3，8，訪問列表為0，0，0，0，1，1。0表示訪問過。所以繼續(xù)下一層，然后就剩下組合節(jié)點3和8了，取3左邊的長度為0.666，8右邊的長度為0.375。相加為1.041再加上1就是2.041，超過房間寬度，那么這種情況就不符合，繼續(xù)循環(huán)這次是8和3，取8的左邊為0.625取3的右邊0.3，還是超過，不符合，沒有可訪問節(jié)點，回溯。回溯到第二層，目前循環(huán)到剛剛是3和5，5訪問過不符合，下面就繼續(xù)訪問節(jié)點4也就是重量3，是組合節(jié)點有其左右長度，分別為0.666和0.333，一開始是3和3取也就是節(jié)點2和節(jié)點4，取2節(jié)點左邊長度為0，4節(jié)點右邊長度為0.333，總長度為1.333，將節(jié)點6重量為6添加到節(jié)點列表中，節(jié)點列表為1，2，3，5，3，6，節(jié)點6左右長度分別是0.5和0.8333。可以進行下一層，訪問列表為0，0，0，1，0，1。可訪問的節(jié)點是3和6，然后取3的左邊和6的右邊，不符合，循環(huán)，取6的左邊和3的右邊為0.5+1<1.7041，符合條件，達到頂層，退出和當前最大比較。回溯下一個。以此類推可以訪問過所有節(jié)點組成的所有二叉樹。

代碼部分：

#include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include<iostream> using namespace std; const int maxn = 20; double lw[maxn], rw[maxn], r; int w[maxn], vis[maxn]; int indexw = 0; int n; double ans; void dfs(int layer) {if (layer == n)return;for (int i = 0; i < maxn; i++) {if (vis[i]) {for (int j = 0; j < maxn; j++) {if (i != j && vis[j]) {double L = max(lw[i], lw[j] - 1); double R = max(rw[j], rw[i] - 1);//防止右邊的節(jié)點的左長度超過左邊節(jié)點的左長度，同理右也是if (L + R + 1 < r) {//判斷是否小于房間長度if (layer == n - 1)ans = max(ans, L + R + 1);vis[i] = vis[j] = 0;//置為訪問過int id = indexw++;vis[id] = 1;//新節(jié)點置為可訪問w[id] = w[i] + w[j];//新節(jié)點重量為兩節(jié)點之和lw[id] = w[j]*1.0 / w[id] + L;//不能忘記加上之前的右邊長度rw[id] = w[i]*1.0 / w[id] + R;dfs(layer + 1);vis[i] = vis[j] = 1;vis[--indexw] = 0;//新節(jié)點要置為不可訪問！}}}}} } int main() {int kase;cin >> kase;while (kase-- > 0) {indexw = 0; ans = -1;memset(vis, 0, sizeof(w));memset(lw, 0, sizeof(lw));memset(rw, 0, sizeof(rw));cin >>r>> n;for (int i = 0; i < n; i++) { cin >> w[i]; vis[indexw++] = 1; }if (n == 1) { printf("0.0000000000\n"); continue; }dfs(1);printf("%.10lf\n", ans);}return 0; }

?老師的代碼是玄學(xué)（表示學(xué)不來）

// UVa1354 Mobile Computing // Rujia Liu #include<cstdio> #include<cstring> #include<vector> using namespace std; struct Tree {double L, R; // distance from the root to the leftmost/rightmost pointTree():L(0),R(0) {} }; const int maxn = 6; int n, vis[1<<maxn]; double r, w[maxn], sum[1<<maxn]; vector<Tree> tree[1<<maxn]; void dfs(int subset) {if(vis[subset]) return;vis[subset] = true;bool have_children = false;for(int left = (subset-1)&subset; left; left = (left-1)&subset) {have_children = true;int right = subset^left;double d1 = sum[right] / sum[subset];double d2 = sum[left] / sum[subset];dfs(left); dfs(right);for(int i = 0; i < tree[left].size(); i++)for(int j = 0; j < tree[right].size(); j++) {Tree t;t.L = max(tree[left][i].L + d1, tree[right][j].L - d2);t.R = max(tree[right][j].R + d2, tree[left][i].R - d1);if(t.L + t.R < r) tree[subset].push_back(t);}}if(!have_children) tree[subset].push_back(Tree()); }int main() {int T;scanf("%d", &T);while(T--) {scanf("%lf%d", &r, &n);for(int i = 0; i < n; i++) scanf("%lf", &w[i]);for(int i = 0; i < (1<<n); i++) {sum[i] = 0;tree[i].clear();for(int j = 0; j < n; j++)if(i & (1<<j)) sum[i] += w[j];}int root = (1<<n)-1;memset(vis, 0, sizeof(vis));dfs(root);double ans = -1;for(int i = 0; i < tree[root].size(); i++)ans = max(ans, tree[root][i].L + tree[root][i].R);printf("%.10lf\n", ans);}return 0; }

他用的是二進制枚舉子集，每次都取出左右子集，枚舉集合的所有子集，最后進行子集判斷，果然厲害。

總結(jié)

以上是生活随笔為你收集整理的UVA1354天平难题 枚举二叉树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。