首页 > 代码库 > UVa1354 Mobile Computing (枚举二叉树)
UVa1354 Mobile Computing (枚举二叉树)
链接：http://acm.hust.edu.cn/vjudge/problem/41537
分析：二进制法枚举二叉树。用n位二进制位代表n个元素，第i位为1代表集合中包含第i个元素，否则不包含。从右往左依次表示第0,1,2,3...n-1号元素，sum表示包含集合中的元素时的总重量，tree[subset]表示包含集合中的元素时天平合法的L和R，vis表示当前子集是否已经被枚举过避免重复枚举。然后就是dfs递归枚举子集，枚举左子树的集合剩下的就是右子树，然后继续递归枚举，枚举到叶子结点或vis为true时终止且叶子结点的L和R为0，然后循环遍历subset的left和right，将subset下合法的L和R存到tree[subset]中。最后找到tree[root]中最大的L+R就是答案。1 #include<cstdio> 2 #include<cstring> 3 #include<vector> 4 using namespace std; 5 6 struct Tree { 7 double L, R; 8 Tree():L(0),R(0) {} 9 };10 11 const int maxn = 6;12 13 int n, vis[1 << maxn];14 double r, w[maxn], sum[1 << maxn];15 vector<Tree> tree[1 << maxn];16 17 void dfs(int subset) {18 if(vis[subset]) return;19 vis[subset] = true;20 bool have_children = false;21 for (int left = (subset - 1) & subset; left; left = (left - 1) & subset) {22 have_children = true;23 int right = subset ^ left;24 double d1 = sum[right] / sum[subset];25 double d2 = sum[left] / sum[subset];26 dfs(left); dfs(right);27 for(int i = 0; i < tree[left].size(); i++)28 for(int j = 0; j < tree[right].size(); j++) {29 Tree t;30 t.L = max(tree[left][i].L + d1, tree[right][j].L - d2);31 t.R = max(tree[right][j].R + d2, tree[left][i].R - d1);32 if(t.L + t.R < r) tree[subset].push_back(t);33 }34 }35 if(!have_children) tree[subset].push_back(Tree());36 }37 38 int main() {39 int T;40 scanf("%d", &T);41 while(T--) {42 scanf("%lf%d", &r, &n);43 for(int i = 0; i < n; i++) scanf("%lf", &w[i]);44 for(int i = 0; i < (1<<n); i++) {45 sum[i] = 0;46 tree[i].clear();47 for(int j = 0; j < n; j++)48 if(i & (1 << j)) sum[i] += w[j];49 }50 int root = (1 << n) - 1;51 memset(vis, 0, sizeof(vis));52 dfs(root);53 double ans = -1;54 for(int i = 0; i < tree[root].size(); i++)55 ans = max(ans, tree[root][i].L + tree[root][i].R);56 printf("%.10lf\n", ans);57 }58 return 0;59 }
UVa1354 Mobile Computing (枚举二叉树)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。