hdu4035之经典慨率DP

hdu4035之经典慨率DP

大家好,又见面了,我是全栈君。

Maze

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65768/65768 K (Java/Others)
Total Submission(s): 1419    Accepted Submission(s): 511
Special Judge




Problem Description
When wake up, lxhgww find himself in a huge maze.

The maze consisted by N rooms and tunnels connecting these rooms. Each pair of rooms is connected by one and only one path. Initially, lxhgww is in room 1. Each room has a dangerous trap. When lxhgww step into a room, he has a possibility to be killed and restart from room 1. Every room also has a hidden exit. Each time lxhgww comes to a room, he has chance to find the exit and escape from this maze.

Unfortunately, lxhgww has no idea about the structure of the whole maze. Therefore, he just chooses a tunnel randomly each time. When he is in a room, he has the same possibility to choose any tunnel connecting that room (including the tunnel he used to come to that room).

What is the expect number of tunnels he go through before he find the exit?

 


Input
First line is an integer T (T ≤ 30), the number of test cases.

At the beginning of each case is an integer N (2 ≤ N ≤ 10000), indicates the number of rooms in this case.

Then N-1 pairs of integers X, Y (1 ≤ X, Y ≤ N, X ≠ Y) are given, indicate there is a tunnel between room X and room Y.

Finally, N pairs of integers Ki and Ei (0 ≤ Ki, Ei ≤ 100, Ki + Ei ≤ 100, K1 = E1 = 0) are given, indicate the percent of the possibility of been killed and exit in the ith room.

 


Output
For each test case, output one line “Case k: ”. k is the case id, then the expect number of tunnels lxhgww go through before he exit. The answer with relative error less than 0.0001 will get accepted. If it is not possible to escape from the maze, output “impossible”.

 


Sample Input
   
   
3 3 1 2 1 3 0 0 100 0 0 100 3 1 2 2 3 0 0 100 0 0 100 6 1 2 2 3 1 4 4 5 4 6 0 0 20 30 40 30 50 50 70 10 20 60

 


Sample Output
   
   
Case 1: 2.000000 Case 2: impossible Case 3: 2.895522

有一颗树n个结点n-1条边,根结点为1

对于在点i下一步有3种情况:

1:被杀死回到点1 — 概率为ki

2:找到出口退出—-慨率为ei

3:沿着边进入下一个点

求从点1開始到退出的平均须要走的边数

/*分析:
对于点i:
1,点i是叶子结点,则:
E(i)=ki*E(1)+ei*0+(1-ki-ei)*(E(father)+1)
=>E(i)=ki*E(1)+(1-ki-ei)*E(father)+(1-ki-ei)
2,点i非叶子结点,则:
E(i)=ki*E(1)+ei*0+(1-ki-ei)/m *(E(father)+1)+(1-ki-ei)/m*SUM(E(child)+1)
=>E(i)=ki*E(1)+(1-ki-ei)/m *E(father)+(1-ki-ei)/m*SUM(E(child))+(1-ki-ei);//作为1式 

从公式可知求E(i)须要求到E(father),E(child)
但这是非常难求到的,由于即使是叶子结点也须要知道E(1),可是E(1)是未知的须要求的

如果:E(i)=Ai*E(1)+Bi*E(father)+Ci;//作为2式

所以:E(child)=Aj*E(1)+Bj*E(i)+Cj;
=>SUM(E(child))=SUm(Aj*E(1)+Bj*E(i)+Cj);
带入1式 
 =>E(i)=ki*E(1)+(1-ki-ei)/m *E(father)+(1-ki-ei)/m*SUm(Aj*E(1)+Bj*E(i)+Cj)+(1-ki-ei);
 =>(1-(1-ki-ei)/m*SUM(Bj))*E(i)=(ki+(1-ki-ei)/m*SUM(Aj))*E(1)+(1-ki-ei)/m *E(father)+(1-ki-ei+(1-ki-ei)/m*SUM(cj));
 与上述2式对照得到:
 Ai=(ki+(1-ki-ei)/m*SUM(Aj))       / (1-(1-ki-ei)/m*SUM(Bj))
 Bi=(1-ki-ei)/m                   / (1-(1-ki-ei)/m*SUM(Bj))
 Ci=(1-ki-ei+(1-ki-ei)/m*SUM(cj)) / (1-(1-ki-ei)/m*SUM(Bj))
 所以Ai,Bi,Ci仅仅与i的孩子Aj,Bj,Cj和本身ki,ei有关
 于是能够从叶子開始逆推得到A1,B1,C1
 在叶子节点:
 Ai=ki;
 Bi=(1-ki-ei);
 Ci=(1-ki-ei);
 而E(1)=A1*E(1)+B1*0+C1;
 =>E(1)=C1/(1-A1);
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <iomanip>
#define INF 99999999
typedef long long LL;
using namespace std;

const int MAX=10000+10;
const double eps=1e-9;
int n,size;
int head[MAX];
double A,B,C,k[MAX],e[MAX];

struct Edge{
	int v,next;
	Edge(){}
	Edge(int V,int NEXT):v(V),next(NEXT){}
}edge[MAX*2];

void Init(){
	memset(head,-1,sizeof head);
	size=0;
}

void InsertEdge(int u,int v){
	edge[size]=Edge(v,head[u]);
	head[u]=size++; 
}

void dfs(int u,int father){
	double a=0,b=0,c=0,p;
	int m=0;
	for(int i=head[u]; i != -1;i=edge[i].next){
		int v=edge[i].v;
		if(v == father)continue;
		dfs(v,u);
		a+=A;
		b+=B;
		c+=C;
		++m;
	}
	if(father != -1)++m;
	p=(1-k[u]-e[u])/m;
	A=(k[u]+p*a)/(1-p*b);
	B=p/(1-p*b);
	C=(1-k[u]-e[u]+p*c)/(1-p*b);
}

int main(){
	int t,u,v,num=0;
	scanf("%d",&t);
	while(t--){
		scanf( "%d",&n);
		Init();
		for(int i=1;i<n;++i){
			scanf("%d%d",&u,&v);
			InsertEdge(u,v);
			InsertEdge(v,u);
		}
		for(int i=1;i<=n;++i){
			scanf("%lf%lf",&k[i],&e[i]);
			k[i]/=100;
			e[i]/=100;
		} 
		dfs(1,-1);
		if(fabs(A-1)<eps)printf("Case %d: impossible\n",++num);
		else printf("Case %d: %.6f\n",++num,C/(1-A));
	}
	return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115355.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • SPPnet详解

    SPPnet详解RCNN系列:RCNN,SPPNet,FastRCNN,FasterRCNN,R-FCN。作者是何凯明SPPNet出现的原因之前的网络,比如LeNet,AlexNet,ZF,VGG等,它们的输入都是固定大小的,为什么要固定大小呐?原因就在最后连接的全连接层上。全连接层的输入一定是固定大小的。这一点很容易理解,因为全连接层网络就是传统的神经网络,传统的神经网络的输入层必定是固定大小的。而卷积神经网络的conv层的输入并不需要固定大小,那么conv层不用固定大小,FC层的输入又要固定大小,那么在这两

  • JavaScript语言基础知识7

    JavaScript语言基础知识7

  • Apache规则RewriteCond详解

    Apache规则RewriteCond详解
    Apache中RewriteCond语句对于我来说一直是个难点,多次试图去把它搞明白,都没有结构,这次我终于算大概知道它的意思了。 RewriteCond就像我们程序中的if语句一样,表示如果符合某个或某几个条件则执行RewriteCond下面紧邻的RewriteRule语句,这就是RewriteCond最原始、基础的功能,为了方便理解,下面来看看几个例子。
      RewriteEngineon
      RewriteCond %{HTTP_USER_AGENT

  • WebGame开发

    WebGame开发web策略类游戏开发(六)缓存概述 公布一个小webgame代码 webgame创意之《吞噬者》 webgame创意之《超时空要塞之边境》 webgame创意之《坐庄》 web策略类游戏开发(五)数据库表设计web策略类游戏开发(四)一个可以承载万人在线的架

  • idea激活服务器 3月最新注册码

    idea激活服务器 3月最新注册码,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • dynamic-css 动态 CSS 库,使得你可以借助 MVVM 模式动态生成和更新 css,从 js 事件和 css 选择器的苦海中脱离出来

    dynamic-css 动态 CSS 库,使得你可以借助 MVVM 模式动态生成和更新 css,从 js 事件和 css 选择器的苦海中脱离出来

    2021年11月24日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号