首页 > 代码库 > HDU 4035

HDU 4035

2024-08-03 09:53:55   218人阅读

 dp求期望的题。    设 E[i]表示在结点i处，要走出迷宫所要走的边数的期望。E[1]即为所求。    叶子结点：    E[i] = ki*E[1] + ei*0 + (1-ki-ei)*(E[father[i]] + 1);         = ki*E[1] + (1-ki-ei)*E[father[i]] + (1-ki-ei);    非叶子结点：（m为与结点相连的边数）    E[i] = ki*E[1] + ei*0 + (1-ki-ei)/m*( E[father[i]]+1 + ∑( E[child[i]]+1 ) );         = ki*E[1] + (1-ki-ei)/m*E[father[i]] + (1-ki-ei)/m*∑(E[child[i]]) + (1-ki-ei);    设对每个结点：E[i] = Ai*E[1] + Bi*E[father[i]] + Ci;    对于非叶子结点i，设j为i的孩子结点，则    ∑(E[child[i]]) = ∑E[j]                   = ∑(Aj*E[1] + Bj*E[father[j]] + Cj)                   = ∑(Aj*E[1] + Bj*E[i] + Cj)    带入上面的式子得    (1 - (1-ki-ei)/m*∑Bj)*E[i] = (ki+(1-ki-ei)/m*∑Aj)*E[1] + (1-ki-ei)/m*E[father[i]] + (1-ki-ei) + (1-ki-ei)/m*∑Cj;    由此可得    Ai =        (ki+(1-ki-ei)/m*∑Aj)   / (1 - (1-ki-ei)/m*∑Bj);    Bi =        (1-ki-ei)/m            / (1 - (1-ki-ei)/m*∑Bj);    Ci = ( (1-ki-ei)+(1-ki-ei)/m*∑Cj ) / (1 - (1-ki-ei)/m*∑Bj);    对于叶子结点    Ai = ki;    Bi = 1 - ki - ei;    Ci = 1 - ki - ei;    从叶子结点开始，直到算出 A1,B1,C1;    E[1] = A1*E[1] + B1*0 + C1;    所以    E[1] = C1 / (1 - A1);    若 A1趋近于1则无解...

 经典DP期望了。以上是题解了，其实这道题是最开始做的，所以后来才会用那种设系数的方法。一直留到现在才写，自己重新推了一遍，感觉这种设系数然后递推系数的方法实在妙极啊。。

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#define N 10010struct ed{	int u,v;	int next;}edge[N*2];int head[N];struct nd{	double k,e;}node[N];int tot,n;double A[N],B[N],C[N];void addedge(int u,int v){	edge[tot].u=u;	edge[tot].v=v;	edge[tot].next=head[u];	head[u]=tot++;}void dfs(int parent,int now){	bool leaf=true;	double tcA,tcB,tcC;	tcA=tcB=tcC=0;	int cnt=0;	double ki=node[now].k;	double ei=node[now].e;	for(int e=head[now];e!=-1;e=edge[e].next){		cnt++;		if(edge[e].v!=parent){			leaf=false;			dfs(now,edge[e].v);			tcA+=A[edge[e].v];			tcB+=B[edge[e].v];			tcC+=C[edge[e].v];		}	}	if(leaf){		A[now]=ki;		B[now]=1-ki-ei;		C[now]=1-ki-ei;	}	else{		A[now]=(ki+tcA*(1-ki-ei)/cnt)/(1-tcB*(1-ki-ei)/cnt);		B[now]=(1-ki-ei)/cnt/(1-tcB*(1-ki-ei)/cnt);		C[now]=(tcC*(1-ki-ei)/cnt+(1-ki-ei))/(1-tcB*(1-ki-ei)/cnt);	}}int main(){	int T,u,v,kase=0;	double k,e;	scanf("%d",&T);	while(T--){		scanf("%d",&n);		for(int i=1;i<=n;i++){			head[i]=-1;			A[i]=B[i]=C[i]=0;		}		tot=0;		for(int i=1;i<n;i++){			scanf("%d%d",&u,&v);			addedge(u,v);			addedge(v,u);		}		for(int i=1;i<=n;i++){			scanf("%lf%lf",&k,&e);			node[i].k=k/100;			node[i].e=e/100;		}		dfs(0,1);		double ans=(C[1])/(1-A[1]);		if(fabs(1-A[1])<1e-9)   //必须是-9。。。跪了。。 		printf("Case %d: impossible\n",++kase);		else{			printf("Case %d: %.6lf\n",++kase,ans);		}	}	return 0;}

　　

HDU 4035


联系
我们