連MAZE這種題我都做了好久我弱爆了……

http://gnaggnoyil.blogspot.com/2011/09/maze.html

HDU4035,11號網絡賽的MAZE,這道遞推因為我把幾個區域變量【優化】到了全局結果一直WA,然後我就禿了……
算法:
這個禿雖然是個無根樹,但是由於樹根是確定的了,所以實質上就是個有根樹.設e[i]是以點i為子樹走出迷宮所需的數學期望,那麼可以【得知】,對於任意
一個e[i],其結果一定是一個關於e[1],e[fa[i]]的一次多項式,即我們這裡可以設
e[i]=r[i]*e[1]+x[i]*e[fa[i]]+a[i].那麼對於任意一個點i,都有e[i]=k[i]*e[1]+tmp[i]*
(e[fa[i]]+sum(e[j],j為i的兒子)+1),其中tmp[i]=(1-k[i]-e[i])/cnt[i],cnt[i]即點i的
度..又因為e[fa[j]]=e[i],j是i的兒子,所以,我們可以發現,e[i]中的三個係數r[i],x[i]和a[i]都可以由i的兒子節點們
給遞推出來.這樣遞推到最後,這種會發現e[1]=r[1]*e[1]+a[1],此時就相當於解一個關於e[1]的一元一次方程,解出來即可.
source code:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#define maxn 10010
#define eps (1e-10)
#define clr(a) memset(a,0,sizeof(a))
struct edge{
int vt,next;
};
edge e[maxn*5];
double K[maxn],E[maxn],r[maxn],x[maxn],a[maxn],tmp[maxn];
int fa[maxn],cnt[maxn],st[maxn];
bool vis[maxn];
int testcase,n,tot,p,q;
double ttmp;
bool flag;
int sig(double x){
return (x>eps)-(x<-eps);
}
int addedge(int u,int v){
e[++tot].vt=v,e[tot].next=st[u],st[u]=tot;
return 0;
}
int dfs1(int u){
cnt[u]=0;
for(int i=st[u];i!=0;i=e[i].next){
++cnt[u];
if(!vis[e[i].vt])
vis[e[i].vt]=true,fa[e[i].vt]=u,dfs1(e[i].vt);
}
tmp[u]=(1-K[u]-E[u])/cnt[u];
return 0;
}
int dfs2(int u){
if(vis[u])
return 0;
vis[u]=true;
r[u]=x[u]=a[u]=0;
double R=0,X=0,A=cnt[u];
for(int i=st[u];i!=0;i=e[i].next){
if(e[i].vt==fa[u])
continue;
dfs2(e[i].vt);
R+=r[e[i].vt],X+=x[e[i].vt],A+=a[e[i].vt];
}
R*=tmp[u],X*=tmp[u],A*=tmp[u];
if(sig(ttmp=1-X)==0)
flag=false;
if(flag)
r[u]=(K[u]+R)/ttmp,x[u]=tmp[u]/ttmp,a[u]=A/ttmp;
return 0;
}
int main(){
scanf("%d",&testcase);
for(int ttestcase=1;ttestcase<=testcase;++ttestcase){
printf("Case %d: ",ttestcase);
clr(st);
scanf("%d",&n);
tot=0;
for(int i=1;i<n;i++){
scanf("%d%d",&p,&q);
addedge(p,q),addedge(q,p);
}
for(int i=1;i<=n;i++){
scanf("%lf%lf",K+i,E+i);
K[i]/=100.0,E[i]/=100.0;
}
flag=true;
clr(vis),vis[1]=true;
dfs1(1);
clr(vis),vis[1]=true;
for(int i=2;i<=n;i++)
dfs2(i);
if(!flag){
printf("impossible\n");
continue;
}
double X=0,A=0;
for(int i=st[1];i!=0;i=e[i].next)
X+=x[e[i].vt]+r[e[i].vt],A+=a[e[i].vt]+1;
X*=tmp[1],A*=tmp[1];
if(sig(ttmp=1-X)==0){
printf("impossible\n");
continue;
}
printf("%.6lf\n",A/ttmp);
}
return 0;
}