UVA-1354(ポインタ接点の連携方法‖高効率アルゴリズム複雑度算出なし)

ポインタ接点連合、すなわち各ポインタが実際のnodeを指し、新しいnodeを共同で申請し、新しいポインタで表す.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<queue>
#include <vector>
#include <iostream>
using namespace std;

const int maxn = 7;
typedef struct node *pointer;
struct node{
double weight,leftw,rightw,zhong;
node *left,*right;
node():left(NULL),right(NULL){}
};
int n;
double w[maxn],r;
double res=-1;

double cal_wei(pointer root,int floor){
if(root->left==NULL&&root->right==NULL){
    root->leftw=root->rightw=0;
    return root->weight;
}
    root->leftw=cal_wei(root->left,floor+1);
    root->rightw=cal_wei(root->right,floor+1);
    return root->leftw+root->rightw;
}

double Min,Max;
void cal_posi(pointer root){
if(root->left==NULL&&root->right==NULL){
        return ;
}
root->left->zhong=root->zhong-root->rightw/(root->rightw+root->leftw);
root->right->zhong=root->leftw/(root->rightw+root->leftw)+root->zhong;
Max=max(Max,root->right->zhong);
Min=min(Min,root->left->zhong);
cal_posi(root->left); cal_posi(root->right);
}
void dfs(int num,vector<pointer>& now){
if(num==1){
     cal_wei(now[0],0);
     now[0]->zhong=0;
     Min=10000; Max=-10000;
     cal_posi(now[0]);
     if(Max-Min>=0&&Max-Min<=r){
        res=max(res,Max-Min);
     }
     return ;
}

<pre name="code" class="html">//     ，       ；
for(int i=0;i<num;i++)
 for(int j=0;j<num;j++) if(i!=j){    //       ， （6*5）*(5*4)*(4*3)*(3*2)*(2*1)*6*10*2 = 10368000;
     vector<pointer> next;        //             ；                 dfs  
     pointer x=now[i],y=now[j];
     for(int k=0;k<num;k++) if(k!=i&&k!=j) next.push_back(now[k]);
     pointer temp=new node();
     temp->weight=-1; temp->left=x; temp->right=y;
     next.push_back(temp);
     dfs(num-1,next);
}
}
int main()
{
  int T;
  scanf("%d",&T);

  while(T--){
    scanf("%lf %d",&r,&n);
    vector<pointer> ans;
    double x;
    for(int i=1;i<=n;i++){
        scanf("%lf",&x);
        pointer temp=new node();
        temp->weight=x;
        ans.push_back(temp);
    }
    if(n==1) {
        double t=0; printf("%.9lf
",t); continue;
    }
    res=-1000;
    dfs(n,ans);
    if(res==-1000) printf("-1
");
    else printf("%.9lf
",res);
  }
  return 0;
}

 
 
下面为高效算法；
 
 
用到子集的枚举技巧，node【i】里存的为所有子树姿态下的最优长度； 
 
  
  
 
由于使用
 
  
 
#include <stdio.h>
#include <string.h>
#include <vector>
#define INF 0x3f3f3f3f
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int N = 6;
const int MAXN = (1<<N);
int t, n, i, j, vis[MAXN];
double w[N], sumw[MAXN], r;
struct Node {
	double l, r;
	Node() {}
	Node(double ll, double rr) {l = ll; r = rr;}
};
vector<Node> node[MAXN];

int bitcount(int x) {
	if (x == 0) return 0;
	return bitcount(x/2) + (x&1);
}

void dfs(int s) {
	if (vis[s]) return;
	vis[s] = 1;
	if (bitcount(s) == 1) {
		node[s].push_back(Node(0, 0));
		return;
	}
	for (int l = (s - 1)&s ; l > 0; l = (l - 1)&s)  { //   1（ 11001）       ，   （2^(bitcount（s）-2)）
		int r = s^l;
		dfs(l); dfs(r);
		for (int i = 0; i < node[l].size(); i++) {
			for (int j = 0; j < node[r].size(); j++) {
				double ll =min(-sumw[r] / (sumw[l] + sumw[r]) + node[l][i].l,sumw[l] / (sumw[l] + sumw[r]) + node[r][j].l);
				double rr =max(sumw[l] / (sumw[l] + sumw[r]) + node[r][j].r,-sumw[r] / (sumw[l] + sumw[r]) + node[l][i].r);
            
   
                                node[s].push_back(Node(ll, rr));
			}
		}
	}
}

void solve() {
	double ans = -1;
	int s = (1<<n) - 1;
	dfs(s); //printf("%d***
",node[s].size());  node[s].size()                   ； 
	for (int i = 0; i < node[s].size(); i++) {
		if (node[s][i].r - node[s][i].l < r) {
			if (node[s][i].r - node[s][i].l > ans)
				ans = node[s][i].r - node[s][i].l;
		}
	}
	if (ans == -1) printf("-1
");
	else printf("%.10lf
", ans);
}

int main() {
	scanf("%d", &t);
	while (t--) {
		memset(vis, 0, sizeof(vis));
		memset(node, 0, sizeof(node));
		scanf("%lf%d", &r, &n);
		for (i = 0; i < n; i++)
			scanf("%lf", &w[i]);
		for (i = 0; i < (1<<n); i++) {
			sumw[i] = 0;
			for (j = 0; j < n; j++) {
				if (i&(1<<j))
					sumw[i] += w[j];
			}
		} //         
		solve();
	}
	return 0;
}