数据结构与算法实验题6.1 s_sin’s bonus byFZuer

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

玩家从n 个点n-1 条边的图，从节点1 丢下一个小球，小球将由于重力作用向下落，而
从小球所在点延伸出的每一条边有一个值pi 为小球通过该条边的概率（注意从同一个节点
向下延伸的所有边的pi 的和可以小于1，也可以大于1，并且保证对于单独的一条边不会出
现pi>1 的情况），而对于所有处于最下方的节点（如图红点所示）都可以有一个值vi，代
表玩家可以获得的奖励。现在老板给你这样一张图，之后给你n 个vi 的值，老板希望玩家
可以获得的奖励的期望值最小。（对题目不理解可以参见样例）
Ps：小球不会逆着重力往回滚QAQ。保证所给出的图无重边。
★数据输入
输入第一行为一个正整数N (2 < N < 10000)，表示有n 个节点，编号为1 到N。
接下来N-1 行，每行三个整数a b pi ，表示从a，b 之间有一条路径，经过这条路径的
可能性为pi。
接下来一行为有n 个整数，表示n 个vi 的值（10000>=vi>0）。
★数据输出

输入第一行为一个正整数N (2 < N < 10000)，表示有n 个节点，编号为1 到N。
接下来N-1 行，每行三个整数a b pi ，表示从a，b 之间有一条路径，经过这条路径的
可能性为pi。
接下来一行为有n 个整数，表示n 个vi 的值（10000>=vi>0）。
★数据输出
对于每个询问，输出一行一个数精度要求为.10lf，表示最小的奖励期望值。
输入示例输出示例
7

1 2 0.8
1 3 0.2
2 4 1.0
4 7 1.0
3 5 0.7
3 6 0.3
1 2 3 4 5 6 7
1.2600000000

表示题目看了好久才懂~（最后的n个vi值不一定全部需要用到，根据建立的二叉树，才能确定需要用到多少个）

开始没弄懂父节点数组表示法，按照自己的思路做，写了一个好搞笑的代码，然后又尝试用孩子链表表示法做还是行不通，然后又认真研究了一下父节点数组表示法，看到这个代码，顿时豁然开朗：

#include <iostream>
using namespace std; #define MAX_TREE_SIZE 100
typedef struct //节点结构
{
char data;
int parent; //双亲位置域
}PTNode; typedef struct //树结构
{
PTNode node[MAX_TREE_SIZE];
int count; //根的位置和节点个数
}PTree; //初始化树
void init_ptree(PTree &tree)
{
tree.count=-;
}
//添加节点
void add_ptnode(PTree &tree, PTNode ptnode)
{
tree.count++;
tree.node[tree.count].data = ptnode.data;
tree.node[tree.count].parent = ptnode.parent;
}
//输出树
void print_ptree(PTree &tree)
{
int i;
for(i=;i<=tree.count;i++)
{
cout<<" "<<i<<" "<<tree.node[i].data<<" "<<tree.node[i].parent<<endl;
}
}
//前序遍历
void PreOrder(PTree &tree , int num)
{
for(int i=num; i<=tree.count; i++)
{
if(i == num)
{
cout<<" "<<i<<" "<<tree.node[i].data<<" "<<tree.node[i].parent<<endl;
for(int j=num+ ; j<=tree.count; j++)
{
if(tree.node[j].parent == i)
{
PreOrder(tree , j);
}
}
}
}
}//PreOrder
//树没有中序遍历
//后序遍历
void BackOrder(PTree &tree , int num)
{
for(int i=num; i<=tree.count; i++)
{
if(i == num)
{
for(int j=num+ ; j<=tree.count; j++)
{
if(tree.node[j].parent == i)
{
BackOrder(tree , j);
}
}
cout<<" "<<i<<" "<<tree.node[i].data<<" "<<tree.node[i].parent<<endl; }
}
}//BackOrder int main()
{
FILE *fin=fopen("树的表示法.txt","r"); PTree ptree;
init_ptree(ptree);
PTNode ptnode; while(fscanf(fin,"%c%d",&ptnode.data,&ptnode.parent)!=EOF)
{
add_ptnode(ptree,ptnode);
fscanf(fin,"%c%d",&ptnode.data,&ptnode.parent);
}
//输出树
cout<<"数组下标节点值双亲位置"<<endl;
print_ptree(ptree); //前序遍历
//cout<<endl;
//PreOrder(ptree,0); //后序遍历
//cout<<endl;
//BackOrder(ptree,0); fclose(fin);
return ;
}

根据父节点建立的二叉树算法思路，自己写了下面的代码，关键在于后续遍历中，找最后根结点的算法！想了好久，最后还是从数据中找到了规律：

#include<stdio.h> double ans=0.0,a[];
int t=; typedef struct
{
double data; //数据域
int parent; //父节点位置
}PTNode; typedef struct
{
PTNode node[]; //根结构
int count; //根的结点个数
}PTree; PTree ptree;
PTNode ptnode; void add_ptnode(int x1,int x2,double pro)
{
ptree.node[x2].parent=x1; //储存结点的父节点
ptree.node[x2].data=pro*ptree.node[x1].data;//计算权值
} void BackOrder(PTree tree,int num)//后序遍历，递归实现
{
int i,j;
i=num;
if(i<=tree.count)
{
for(j=num+;j<=tree.count;j++)
{
if(tree.node[j].parent==i)//找到该节点的子节点
{
BackOrder(tree,j); //子节点作为新的父节点，向下递归
if((j+i)>tree.count) //分支最低结点算法，判断为（i+j>tree,count）
{
ans+=(a[t]*tree.node[j].data);
t++; } }
} } } int main()
{
int n,i,sit_1,sit_2;
double pro;
scanf("%d",&n);
ptree.count=n;
for(i=;i<=n;i++)
{
ptree.node[i].data=;
} for(i=;i<n-;i++)
{
scanf("%d %d %lf",&sit_1,&sit_2,&pro);
add_ptnode(sit_1,sit_2,pro);
} for(i=;i<n;i++)
{
scanf("%lf",&a[i]);
} BackOrder(ptree,);
printf("%.10lf\n",ans); return ;
}

做题找对算法真的很重要！！！

最终提交代码修改日期：2013-10-29 15:01:21

：

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std; struct PNnode
{
double data;//数据域
int parents;
}; struct PTree
{
PNnode node[];
int count;//节点数
}; PTree ptree;
PNnode pnode;
double ans=0.0,a[],b[];
int t=; int f[]={}; void insert(int x1,int x2,double pro)//插入父节点
{
ptree.node[x2].parents=x1;
ptree.node[x2].data=pro;
f[x1]=;
} /*void search(PTree pt,int n)
{
for(int i=n;i<=pt.count;i++)
{
if(i==n)
{
for(int j=n+1;j<=pt.count;j++)
{
if(pt.node[j].parents==i)
{
pt.node[j].data=pt.node[j].data*pt.node[i].data;
if(f[j]==0)
{
b[t]=pt.node[j].data;
t++;
}
search(pt,j);
}
} }
}
}*/ int main()
{
int n,i,sit_1,sit_2;
double pro;
f[]=;
scanf("%d",&n);
ptree.count=n; for(i=;i<=n;i++)//初始化data
ptree.node[i].data=1.0; for(i=;i<n-;i++)
{
scanf("%d %d %lf",&sit_1,&sit_2,&pro);
insert(sit_1,sit_2,pro);
}
for(i=;i<n;i++)
scanf("%lf",&a[i]); int j=,t=;
for(int q=;q<=ptree.count;q++)
{
if(f[q]==)//最低结点
{
b[t]=1.0;
j=q;
while(j!=)
{
b[t]=b[t]*ptree.node[j].data;
j=ptree.node[j].parents;
//printf("b[%d]=%lf\n",t,b[t]);
}
t++;
}
} //for(i=0;i<t;i++)
// printf("%lf ",b[i]);
//printf("\n");
//for(i=0;i<n;i++)
// printf("%lf ",a[i]);
//printf("\n");
sort(a,a+n);
sort(b,b+t); //for(i=0;i<t;i++)
// printf("%lf ",b[i]);
//printf("\n");
// for(i=0;i<n;i++)
// printf("%lf ",a[i]);
//printf("\n");
for(i=;i<t;i++)
{
ans+=(a[i]*b[t-i-]); } printf("%.10lf\n",ans);
return ;
}