数据结构与算法实验题 6.1 s

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

★实验任务

正如你所知道的 s_sin 是一个非常贪玩的人 QAQ(如果你非常讨厌他请直接从第二段开

始看)，并且令人感到非常遗憾的是，他是一只非常非常穷的 ds，为了改变自己的经济情况

他决定外出打工，但是因为 s_sin 是一只死宅，力量魔法耐力速度运气五围都差到爆表 QAQ。

正当他对人生无比绝望的时候，一个游戏店的老板找到他请他帮助设计一个游戏，并答应给

他一定的报酬。游戏的内容如下：

玩家从 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）。 ★数据输出

对于每个询问，输出一行一个数精度要求为.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 34 5 6 7

1.2600000000

★HINT

分数值最小期望为0.8*1+0.14*2+0.06*3=1.26

图如左图所示

期望值及其公式：http://zh.wikipedia.org/wiki/%E6%9C%9F%E6%9C%9B%E5%80%BC

每次找到和1连通的点，建树，否则就先放着。

父节点表示法~

找父亲的函数直接递归小心栈溢出。（并查集我写多了T T，这个不能路径压缩，而并查集可以）

还有要相信自己，用别人的方法才4分，自己的全A了。哭瞎了

注意的是

2-4表示的是2-4连通，不一定2是4的父亲。

给组样例

7

7 1 0.8

2 7 1.0

4 2 1.0

1 3 0.2

3 6 0.3

5 3 0.7

1 2 3 4 5 6 7

1.26

#include<cstdio>

#include<algorithm>

using namespace std;

const int MAXN=10000+10;

struct Tree

{

	int father;

	double chance;

	bool isleaf;

}a[MAXN];

struct data

{

	int node1;

	int node2;

	double chance;

	bool used;

}text,b[MAXN];

double chance[MAXN];

int reward[MAXN];

int find_root(int cur)

{

	while(a[cur].father!=cur)

	{

		cur=a[cur].father;

	}

	return cur;

}

void creat(int node1,int node2,double temp)

{

	a[node2].father=node1;

	a[node2].chance=temp;

	a[node2].isleaf=true;

	a[node1].isleaf=false;

}

int main()

{

	//freopen("e:\\input.txt","r",stdin);

	int n;

	scanf("%d",&n);

	int i;

	//init

	for(i=0;i<=n;i++)

		a[i].father=i;

	int node1,node2;

	double temp;

	a[1].father=1;

	int b_len=0,b_size=b_len;

	for(i=0;i<n-1;i++)

	{

		scanf("%d%d%lf",&node1,&node2,&temp);

		int root1=find_root(node1);

		int root2=find_root(node2);

		if(root1==1)		//node1已经连接到根

			creat(node1,node2,temp);

		else if(root2==1)    //node2已经连接到根

			creat(node2,node1,temp);

		else

		{

			b[b_len].node1=node1;

			b[b_len].node2=node2;

			b[b_len].chance=temp;

			b[b_len].used=false;

			b_len++;

		}

	}

	b_size=b_len;

	while(b_size!=0)

	{

		for(i=0;i<b_len;i++)

		{

			if(b[i].used==true)

				continue;

			text=b[i];

			node1=text.node1;

			node2=text.node2;

			temp=text.chance;

			b[i].used=true;

			b_size--;

			int root1=find_root(node1);

			int root2=find_root(node2);

			if(root1==1)		//node1已经连接到根

				creat(node1,node2,temp);

			else if(root2==1)    //node2已经连接到根

				creat(node2,node1,temp);

			else

			{

					b[i].used=false;

					b_size++;

			}

		}

	}

	for(i=0;i<n;i++)

		scanf("%d",&reward[i]);

	int len=0,k;

	double t;

	for(i=1;i<=n;i++)

	{

		if(a[i].isleaf==true )

		{

			t=a[i].chance;

			k=a[i].father;

			while(k!=1)

			{

				t*=a[k].chance;

				k=a[k].father;

			}

			chance[len++]=t;

		}

	}

	sort(chance,chance+len);

	sort(reward,reward+n);

	double ans=0;

	for(i=0;i<len;i++)

	{

		ans=ans + chance[ len-i-1 ] * reward[ i ];

	}

	printf("%.10lf\n",ans);

}

巴特西

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

最新文章

热门文章