【hdu4035】Maze

Portal --> hdu4035

Solution

  讲道理不是很懂为啥概d那么喜欢走迷宫qwq

  (推式子推的很爽的一题?)

  首先大力dp列式子

  用(f[i])表示从(i)到离开的期望步数,(du[i])表示(i)点的度数,那么可以得到:

[f[i]=e_i* 0+k_i* f[1]+frac{1-e_i-k_i}{du[i]}sum(f[u]+1) ]

  其中(u)(i)的儿子

  稍微整理一下,对于叶子节点和普通节点我们可以分别得到这样的两条式子:

[egin{aligned} &叶子:f[i]=k_i*f[1]+(1-e_i-k_i)*f[fa(i)]+(1-e_i-k_i)\ \ &普通:f[i]=k_i*f[1]+frac{1-e_i-k_i}{du[i]}*f[fa(i)]+frac{1-e_i-k_i}{du[i]}*sum f[u]+(1-e_i-k_i)\ end{aligned} ]

  考虑从下往上推,那么将(f[u])看成常数的话,其实我们可以将(f[i])表达为(A_i*f[1]+B_i*f[fa(i)]+C_i)这样的形式

  

  这个时候看一下我们要求的答案,可以表示成:(f[1]=A_1*f[1]+B_1*0+C_1)

  那也就是说,(f[1]=frac{C_1}{1-A_1})

  那。。所以其实到最后根本不需要求出所有的(f)值只要知道系数我们就可以直接把答案求出来了(大快人心事!)

  那剩下的就是要想办法把系数求出来

  

  化简一下上面的(f)的表达式

  我们发现(sum f[u])这个东西其实可以写成一个与(f[i])相关的表达式(因为(fa(u)=i)),也就是:

[egin{aligned} sum f[u]&=sum A_u*f[1]+B_u*f[i]+C_u end{aligned} ]

  把这个式子带到上面普通节点的(f)值的表达式里面去,把跟(f[i])有关的放一边,其他放另一边:

[egin{aligned} f[i]&=k_i*f[1]+frac{1-e_i-k_i}{du[i]}*f[fa(i)]+frac{1-e_i-k_i}{du[i]}*(f[1]*sum A_u+f[i]*sum B_u+sum C_u)\ \ (1-frac{1-e_i-k_i}{du[i]}*sum B_u)*f[i]&=(k_i+frac{1-e_i-k_i}{du[i]}*sum A_u)*f[1]+frac{1-e_i-k_i}{du[i]}*f[fa(i)]+frac{1-e_i-k_i}{du[i]}*(sum C_u+du[i]) end{aligned} ]

  
  然后我们就可以得出(、、A、B、C)这三个系数的表达式啦

[egin{aligned} 叶子:&A_i=k_i\ &B_i=1-e_i-k_i\ &C_i=1-e_i-k_i\ \ 普通:&A_i=(k_i+frac{1-e_i-k_i}{du[i]}*sum A_u)/(1-frac{1-e_i-k_i}{du[i]}*sum B_u)\ &B_i=frac{1-e_i-k_i}{du[i]}/(1-frac{1-e_i-k_i}{du[i]}*sum B_u)\ &C_i=frac{1-e_i-k_i}{du[i]}*(sum C_u+du[i])/(1-frac{1-e_i-k_i}{du[i]}*sum B_u)\ end{aligned} ]

  看上去长得。。挺丑。。但是!

  得出了这个式子之后我们就可以从下往上将所有的系数求出来了

​  

  然后就做完了

  那么无解是什么情况呢?应该就是在中间计算过程中,如果有哪一步算的时候除以(0)了就是无解了,中间算的时候判断一下就好了

  

  代码大概长这个样子

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int MAXN=1e4+10;
const double eps=1e-9;
struct xxx{
	int y,nxt;
}a[MAXN*2];
int h[MAXN],du[MAXN];
double A[MAXN],B[MAXN],C[MAXN],k[MAXN],e[MAXN];
int n,m,tot,T;
void add(int x,int y);
bool dfs(int fa,int x);
void init();

int main(){
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
#endif
	int x,y;
	double ans;
	scanf("%d",&T);
	for (int o=1;o<=T;++o){
		printf("Case %d: ",o);
		scanf("%d",&n);
		init();
		for (int i=1;i<n;++i){
			scanf("%d%d",&x,&y);
			add(x,y); add(y,x);
			++du[x]; ++du[y];
		}
		for (int i=1;i<=n;++i){
			scanf("%d%d
",&x,&y);
			k[i]=1.0*x/100.0;
			e[i]=1.0*y/100.0;
		}
		if (dfs(0,1)){
			if (fabs(1-A[1])<=eps) printf("impossible
");
			else
				printf("%.6lf
",C[1]/(1.0-A[1]));
		}
		else
			printf("impossible
");
	}
}

void init(){
	tot=0;
	memset(h,-1,sizeof(h));
	memset(du,0,sizeof(du));
}

void add(int x,int y){
	a[++tot].y=y; a[tot].nxt=h[x]; h[x]=tot;
}

bool dfs(int fa,int x){
	int u,son=0;
	double sum=0;
	A[x]=k[x]; B[x]=(1.0-e[x]-k[x])/(1.0*du[x]); C[x]=du[x];
	for (int i=h[x];i!=-1;i=a[i].nxt){
		u=a[i].y;
		if (u==fa) continue;
		++son;
		if (!dfs(x,u)) return false;
		C[x]+=C[u];
		A[x]+=(1.0-e[x]-k[x])/(1.0*du[x])*A[u];
		sum+=B[u];
	}
	if (son==0){
		A[x]=k[x]; B[x]=1.0-e[x]-k[x]; C[x]=1.0-k[x]-e[x];
	}
	else{
		C[x]*=(1-e[x]-k[x])/(1.0*du[x]);
		sum*=(1.0-e[x]-k[x])/(1.0*du[x]);
		sum=1.0-sum;
		if (fabs(sum)<eps) return false;
		A[x]/=sum;
		B[x]/=sum;
		C[x]/=sum;
	}
	return true;
}
原文地址:https://www.cnblogs.com/yoyoball/p/9129594.html