题解 HDU4035 【Maze】

posted on 2022-08-17 12:33:51 | under 题解 | source

problem

https://vjudge.net/problem/HDU-4035

SHY 在一棵树上随机游走，从根节点出发，每次有 \(k_u\) 的几率回到根节点，\(e_u\) 的几率到达出口，否则随机选择一个与它相连的节点并走过去，求期望多少步能走到出口。\(1\leq n\leq 10^4\)。

solution

令根为 \(1\)，\(t_u=1-k_u-e_u\)，记 \(f_u\) 表示从点 \(u\) 出发走到出口的期望步数，\(p\) 为 \(u\) 的父亲，\(v\) 为 \(u\) 的儿子，\(d\) 为点 \(u\) 的度数。显然有：

我们发现这个式子有后效性，那么当然不能打高斯消元，考虑令 \(f_u=a_u\times f_1+b_u\times f_p+c_u\)。分类讨论：对于一片叶子，显然有 \(a_u=k_u,b_u=c_u=t_u\)。

对于非叶子节点 \(u\)，我们考虑拆掉 \(\sum_{v\in son(u)}f_v=f_1\times\sum a_v+f_u\times\sum b_v+\sum c_v\)。

接下来是点睛之笔：把 \(f_u\) 项移到等式左边！

将 \(1-\frac{t_u}{d}\times\sum b_v\) 作为分母移过去，我们终于得到：

这里的每一项都只和 \(u,v\) 有关，可以做树型 DP 了！自底向上更新 \(a_u,b_u,c_u\) 即可。我们其实并不需要计算 \(f_u\)。

最终的答案是 \(f_1=a_1\times f_1+c_1\)，可化简为 \(f_1=\frac{c_1}{1-a_1}\)。

什么时候会无解呢？分母是 \(0\) 的时候。

• \(d=0\) 根本除不动（？？？？？）
• 计算过程中 \(1-\frac{t_u}{d}\times\sum b_v=0\)，寄。
• 最终 \(a_1=1\)，相减又得 \(0\)，寄。

那么我们可以写代码了。

code

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long LL;
const double eps=1e-9;
template<int N,int M,class T=int> struct graph{
    int head[N+10],nxt[M*2+10],cnt;
    struct edge{
        int u,v;T w;
        edge(int u=0,int v=0,T w=0):u(u),v(v),w(w){}
    } e[M*2+10];
    graph(){memset(head,cnt=0,sizeof head);}
    edge operator[](int i){return e[i];}
    void add(int u,int v,T w=0){e[++cnt]=edge(u,v,w),nxt[cnt]=head[u],head[u]=cnt;}
    void link(int u,int v,T w=0){add(u,v,w),add(v,u,w);}
};
int n,deg[10010];
double a[10010],b[10010],c[10010],k[10010],t[10010];
graph<10010,10010> g;
int dfs(int u,int fa){
	if(deg[u]==1&&fa) return a[u]=k[u],b[u]=c[u]=t[u],1;
    //			^~~~ important!
	double sa=0,sb=0,sc=0;
	for(int i=g.head[u];i;i=g.nxt[i]){
		int v=g[i].v; if(v==fa) continue;
		if(!dfs(v,u)) return 0;
		sa+=a[v],sb+=b[v],sc+=c[v];
	}
	double del=t[u]/deg[u],tmp=1-del*sb;
	if(fabs(tmp)<eps) return 0;
	a[u]=(k[u]+del*sa)/tmp;
	b[u]=del/tmp;
	c[u]=(t[u]+del*sc)/tmp;
	return 1;
}
int mian(){
	for(int i=1,u,v;i<n;i++) scanf("%d%d",&u,&v),g.link(u,v),deg[u]++,deg[v]++;
	for(int u=1;u<=n;u++) scanf("%lf%lf",&k[u],&t[u]),k[u]/=1e2,t[u]/=1e2,t[u]=1-t[u]-k[u];
	if(dfs(1,0)&&fabs(1-a[1])>eps) printf("%.6lf\n",c[1]/(1-a[1]));
	else puts("impossible"); 
	return 0;
}
void reset(){
	static int ccf=0;
	printf("Case %d: ",++ccf);
	memset(a,0,sizeof a);
	memset(b,0,sizeof b);
	memset(c,0,sizeof c);
	memset(k,0,sizeof k);
	memset(t,0,sizeof t);
	memset(deg,0,sizeof deg);
	memset(g.head,g.cnt=0,sizeof g.head); 
}
int main(){
//	#ifdef LOCAL
//	 	freopen("input.in","r",stdin);
//	#endif
	for(scanf("%*d");~scanf("%d",&n);reset(),mian());
	return 0;
}

原文地址：http://www.cnblogs.com/caijianhong/p/solution-HDU4035.html