HDU 4035

 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 10010

struct 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

最新文章

热门文章