接上uva1354 用二进制枚举

copy刘汝佳的模板...不解释了...水平差...

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 6;

struct Tree{
    double L,R;
    Tree():L(0),R(0){}
};

bool visit[1<<maxn];
double room;
int n;
double w[maxn], sum[1<<maxn];
vector<Tree> tree[1<<maxn];

void dfs(int subnet){
    if(visit[subnet]) return; 
    visit[subnet] = true;
    bool hasChild = false;
    int debug_left=(subnet-1)&subnet;
    //printf("subnet:%d left:%d right:%d\n",subnet,debug_left,subnet^debug_left);
    for(int left=(subnet-1)&subnet;left>0;left=(left-1)&subnet)
    {
        hasChild = true;
        int right = subnet^left;
        printf("subnet:%d left:%d right:%d\n",subnet,left,right);
        dfs(left); dfs(right);
        double l = sum[right]/sum[subnet];
        double r = sum[left]/sum[subnet];
        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+l, tree[right][j].L-r);
            t.R=max(tree[right][j].R+r, tree[left][i].R-l);
            if((t.L+t.R)-room<1e-5) tree[subnet].push_back(t);
          }
    }
    if(!hasChild)  tree[subnet].push_back(Tree());
}

int main(){
    int T;
//  freopen("test.txt","r",stdin);
//  freopen("ouput.txt","w",stdout);
    scanf("%d", &T);
    while(T--){
        scanf("%lf", &room);
        scanf("%d", &n);
        memset(w, 0, sizeof(w));
        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];
        }
        memset(visit, false, sizeof(visit));
        int root=(1<<n)-1;
        dfs(root);
        double ans=-1;
        for(int i=0;i<tree[root].size();i++)
          printf("%.10lf\n",tree[root][i].L+tree[root][i].R,tree[root].size());
    }
//  fclose(stdin);
//  fclose(stdout);
    return 0;
}