题目链接：https://vjudge.net/contest/210334#problem/G
转载于：https://blog.****.net/todobe/article/details/54171920
题目描述：
给出房间的宽度r和s个挂坠的重量wi，设计一个尽量宽（但宽度不能超过房间宽度r）的天平，挂着所有挂坠。
天平由一些长度为1的木棍组成。木棍的每一端要么挂一个挂坠，要么挂另外一个木棍。如图1所示，设n和m分别是两端的总重量，要让天平平衡，必须满足n*a=m*b。
例如：如果有3个重量分别为1,1,2的挂坠，有3种平衡的天平，如下图所示：
挂坠的宽度忽略不计，且不同的子天平可以相互重叠。如下图所示，宽度为（1/3）+1+（1/4）。 
输入格式:
输入第一行为数据组数。每组数据前两行为房间宽度r和挂坠数目s （0 < r < 10,1<=s<=6）。以下s行为一个挂坠的重量wi（1<=wi<=1000）。输入保证不存在天平的宽度恰好在r-10^(-5)和r+10^(-5)（这样可以保证不会出现精度问题）。
输出格式:
对于每组数据，输出最优天平的宽度。如果无解，输出-1。你的输出和标准答案的绝对误差不应超过10^(-8)
题目分析：（搜索）
天平的形态最后可以看成二叉树，所以问题转化成了我们有一堆点（点数还不超过6），要把这一堆点合成一颗树。我们可以用哈弗曼树的想法，每次把两个节点合成一个新的节点，最终只剩下一个节点，就是一组可行解，更新答案。
但是我们不知道每次要合并哪两个点，因为层数很少，所以可以暴力枚举。
这是huffman合并思想
#include<cstdio>
#include<iostream>
#include <algorithm>
using namespace std;
struct balance //形象的定义一个带有宽度的'节点'，若该节点不是由节点合并而来的，则ls,和rs为0（因为点的左宽和右宽为0），如果是由其他结点合并而来的，则宽度按照实际宽度更新
{
double w, ls, rs;
balance operator + (const balance c)
{
balance z;
z.w = w + c.w;
double l = c.w / (w + c.w); //木棍左边的长度为，右边的点的重量/(两点的重量之和)
double r = w / (w + c.w); //同理
z.ls = max(l + ls, c.ls - r); //比较右边点的左边界和左边点的左边界哪个更靠左，因为完全有可能右边点的左边界比左边点的左边界还要靠左
z.rs = max(r + c.rs, rs - l); //同理
return z;
}
}a[];
double r, ans;
int s, T;
void dfs(int c)
{
if (c == s) //n个节点最终加到1个节点只需加n-1次
{
].ls + a[].rs; //利用huffman原理，将树的所有节点最终合成一个'节点',整个天平的宽度即为这个‘节点’的宽度
if (cs <= r && cs>ans) ans = cs;
return;
}
balance b[], d[];
; i <= s - c + ; i++) b[i] = a[i]; //记录下当前所枚举的各点的情况
; i <= s - c + ; i++) //这个循环我没弄明白
; j <= s - c + ; j++)
{
if (i == j) continue;
; k <= s - c + ; k++) a[k] = b[k]; //重置为刚才用b[]数组记录下的当前c值得情况
;
; k <= s - c + ; k++)
if (k != i && k != j) d[++top] = a[k];
d[++top] = a[i] + a[j];
; k <= top; k++) a[k] = d[k];
dfs(c + );
}
}
int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%lf%d", &r, &s);
; i <= s; i++)
{
scanf("%lf", &a[i].w);
a[i].ls = ;
a[i].rs = ;
}
ans = -;
dfs();
printf("%.10lf\n", ans);
}
;
}
这是枚举子集思想
- &表示交集，^表示差集，|表示并集。
- 利用交集是否为0还可以判断是否存在包含关系。
- 递归枚举
#include<cstdio>
#include<cstring>
#include<vector>
#include <algorithm>
using namespace std;
struct Tree {
double L, R; // distance from the root to the leftmost/rightmost point
Tree() :L(), R() {}
};
;
<< maxn];
<< maxn];
vector<Tree> tree[ << maxn];
void dfs(int subset) {
if (vis[subset]) return;
vis[subset] = true;
bool have_children = false;//初始化
)⊂ left; left = (left - )&subset) {//遍历每一种情况，取subset的子集所以要取交集，从上一个的集合再取交集可以提高效率
have_children = true;//进入循环表明有子集
int right = subset ^ left;//得到差集
double d1 = sum[right] / sum[subset];//公示推导出来的
double d2 = sum[left] / sum[subset];
dfs(left); dfs(right);
; i < tree[left].size(); i++)
; 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);
; i < n; i++) scanf("%lf", &w[i]);
; i < ( << n); i++) {//遍历每一种可能
sum[i] = ;
tree[i].clear();
; j < n; j++)
<< j)) sum[i] += w[j];//把这个集合中的质量都加起来，包含第j个质量的集合。
}
<< n) - ;//全部都是1
memset(vis, , sizeof(vis));
dfs(root);
;
; i < tree[root].size(); i++)
ans = max(ans, tree[root][i].L + tree[root][i].R);//找到最大值
printf("%.10lf\n", ans);
}
;
}
2018-04-16