刘晓忠 网站建设,响应式网站页面设计,公司网站规划,标书制作员工资很低吗Maze
状态表示#xff1a;fuf_ufu表示在uuu节点走出迷宫期望次数#xff0c;dud_udu表示度数 首先很容易想到下面式子fukuf1(1−ku−eu)∑u→vfv1duf_uk_uf_1(1-k_u-e_u)\frac{\sum _{u\to v}f_v1}{d_u}fukuf1(1−ku−eu)du∑u→vfv1 每个节点有一个类…Maze
状态表示fuf_ufu表示在uuu节点走出迷宫期望次数dud_udu表示度数 首先很容易想到下面式子fuku×f1(1−ku−eu)×∑u→vfv1duf_uk_u×f_1(1-k_u-e_u)×\frac{\sum _{u\to v}f_v1}{d_u}fuku×f1(1−ku−eu)×du∑u→vfv1 每个节点有一个类似的式子也就是nnn个式子nnn个未知量我们需要求出f1f_1f1显然可以高斯消元O(n3)O(n^3)O(n3)但是看了1≤n≤1041\leq n\leq 10^41≤n≤104留下了可惜的泪水~~
之前也做过返回起点的题目只需要在dp时候多记录一维信息于是向初中解方程那样求解即可这样时间复杂度就能优化到O(n)O(n)O(n)不过本题在树上好像也不可行其实可以 对于“返回”在树上是如何体现的
不难想到返回祖先而此题中就是返回父亲以及返回根节点111于是效仿返回题目的做法列出下面方程 fuku×f11−ku−eudu×(ffa1)1−ku−eudu×∑v∈sonu(fv1)f_uk_u×f_1\frac{1-k_u-e_u}{d_u}×(f_{fa}1)\frac{1-k_u-e_u}{d_u}×\sum_{v\in son_u}{(f_v1)}fuku×f1du1−ku−eu×(ffa1)du1−ku−eu×v∈sonu∑(fv1) 稍微化简一下 fuku×f11−ku−eudu×ffa1−ku−eudu×∑v∈sonufv(1−ku−eu)f_uk_u×f_1\frac{1-k_u-e_u}{d_u}×f_{fa}\frac{1-k_u-e_u}{d_u}×\sum_{v\in son_u}{f_v}(1-k_u-e_u)fuku×f1du1−ku−eu×ffadu1−ku−eu×v∈sonu∑fv(1−ku−eu)
我们发现所有dp式子都可以写成 fuau×f1bu×ffacuf_ua_u×f_1b_u×f_{fa}c_ufuau×f1bu×ffacu
由于favufa_vufavu上述式子还能化简得fvav×f1bv×fucvf_va_v×f_1b_v×f_uc_vfvav×f1bv×fucv fuku×f11−ku−eudu×ffa1−ku−eudu×∑v∈sonu(av×f1bv×fucv)(1−ku−eu)f_uk_u×f_1\frac{1-k_u-e_u}{d_u}×f_{fa}\frac{1-k_u-e_u}{d_u}×\sum_{v\in son_u}{(a_v×f_1b_v×f_uc_v)}(1-k_u-e_u)fuku×f1du1−ku−eu×ffadu1−ku−eu×v∈sonu∑(av×f1bv×fucv)(1−ku−eu) 于是有更平凡的式子 (1−1−ku−eudu∑v∈sonubv)×fu(ku1−ku−eudu∑v∈sonuav)×f11−ku−eudu×ffa1−ku−eudu∑v∈sonucv(1−ku−eu)(1-\frac{1-k_u-e_u}{d_u}\sum_{v\in son_u}{b_v})×f_u(k_u\frac{1-k_u-e_u}{d_u}\sum_{v\in son_u}{a_v})×f_1\frac{1-k_u-e_u}{d_u}×f_{fa}\frac{1-k_u-e_u}{d_u}\sum_{v\in son_u}{c_v}(1-k_u-e_u)(1−du1−ku−euv∈sonu∑bv)×fu(kudu1−ku−euv∈sonu∑av)×f1du1−ku−eu×ffadu1−ku−euv∈sonu∑cv(1−ku−eu) 于是有auku1−ku−eudu∑v∈sonuav1−1−ku−eudu∑v∈sonubva_u\frac{k_u\frac{1-k_u-e_u}{d_u}\sum_{v\in son_u}{a_v}}{1-\frac{1-k_u-e_u}{d_u}\sum_{v\in son_u}{b_v}}au1−du1−ku−eu∑v∈sonubvkudu1−ku−eu∑v∈sonuav bu1−ku−eudu1−1−ku−eudu∑v∈sonubvb_u\frac{\frac{1-k_u-e_u}{d_u}}{1-\frac{1-k_u-e_u}{d_u}\sum_{v\in son_u}{b_v}}bu1−du1−ku−eu∑v∈sonubvdu1−ku−eu cu1−ku−eudu∑v∈sonucv(1−ku−eu)1−1−ku−eudu∑v∈sonubvc_u\frac{\frac{1-k_u-e_u}{d_u}\sum_{v\in son_u}{c_v}(1-k_u-e_u)}{1-\frac{1-k_u-e_u}{d_u}\sum_{v\in son_u}{b_v}}cu1−du1−ku−eu∑v∈sonubvdu1−ku−eu∑v∈sonucv(1−ku−eu)
然后树形dpO(n)O(n)O(n)递推即可
#includecstdio
#includecstring
using namespace std;
constexpr int N10010;
constexpr double eps1e-10;
int h[N],e[2*N],ne[2*N],idx;
void add(int a,int b){e[idx]b,ne[idx]h[a],h[a]idx;}
int d[N],n;
double K[N],E[N],T[N],A[N],B[N],C[N];
int sgn(double x)
{if(fabs(x)eps) return 0;if(x0) return -1;return 1;
}
bool dfs(int u,int fa)
{int md[u];A[u]K[u];B[u]T[u]/m;C[u]T[u];double temp0;for(int ih[u];i!-1;ine[i]){int ve[i];if(vfa) continue;if(!dfs(v,u)) return 0;A[u]T[u]/m*A[v];tempT[u]/m*B[v];C[u]T[u]/m*C[v];}if(!sgn(1.0-temp)) return 0;A[u]/(1-temp);B[u]/(1-temp);C[u]/(1-temp);return 1;
}
int main()
{int TT;scanf(%d,TT);for(int ca1;caTT;ca){scanf(%d,n);memset(h,-1,sizeof(int)*(n1));idx0;memset(d,0,sizeof(int)*(n1));for(int i1;in;i){int u,v;scanf(%d%d,u,v);add(u,v),add(v,u);d[u],d[v];}for(int i1;in;i){scanf(%lf%lf,K[i],E[i]);K[i]/100;E[i]/100;T[i]1-K[i]-E[i];}if(dfs(1,0)sgn(1.0-A[1]))printf(Case %d: %.10f\n,ca,C[1]/(1-A[1]));else printf(Case %d: impossible\n,ca);}return 0;
}太秒了吧
