hdu4035 Maze 题解

/*

    设 E[i]表示在结点i处，要走出迷宫所要走的边数的期望。

    E[i] = ki*E[1] + (1-ki-ei)*E[fa[i]] + (1-ki-ei);

    E[i] = ki*E[1] + (1-ki-ei)/siz[i]*E[fa[i]] + (1-ki-ei)/siz[i]*∑(E[child[i]]) + (1-ki-ei);

    设对每个结点：E[i] = Ai*E[1] + Bi*E[fa[i]] + Ci;

    ∑(E[child[i]])  = ∑E[j] = ∑(Aj*E[1] + Bj*E[i] + Cj)

    带入得

    (1 - (1-ki-ei)/siz[i]*∑Bj)*E[i] = (ki+(1-ki-ei)/siz[i]*∑Aj)*E[1] + (1-ki-ei)/siz[i]*E[fa[i]] + (1-ki-ei) + (1-ki-ei)/siz[i]*∑Cj;

    Ai = (ki+(1-ki-ei)/siz[i]*∑Aj) / (1 - (1-ki-ei)/siz[i]*∑Bj);

    Bi = (1-ki-ei)/siz[i] / (1 - (1-ki-ei)/siz[i]*∑Bj);

    Ci = ( (1-ki-ei)+(1-ki-ei)/siz[i]*∑Cj ) / (1 - (1-ki-ei)/siz[i]*∑Bj);

    E[1] = A1*E[1] + B1*0 + C1;

    E[1] = C1 / (1 - A1);

    上述式子中若分母为零则无解

*/

#include <cstdio>

#include <iostream>

#include <cstring>

#include <cmath>

using namespace std;

const int maxn=1e4+5;

struct edge

{

    int v,nxt;

}ep[maxn<<1];

int hd[maxn],kh;

double k[maxn],e[maxn],a[maxn],b[maxn],c[maxn];

int n,t,siz[maxn];

void add(int u,int v) {ep[++kh]=(edge){v,hd[u]};hd[u]=kh;}

bool dfs(int u,int fa)

{

    double x1=0;

    a[u]=k[u];b[u]=(1-k[u]-e[u])/siz[u];c[u]=1-k[u]-e[u];

    for(int i=hd[u];i!=-1;i=ep[i].nxt)

    {

        if(ep[i].v==fa) continue;

        if(!dfs(ep[i].v,u)) return 0;

        a[u]+=b[u]*a[ep[i].v];

        x1+=b[u]*b[ep[i].v];

        c[u]+=b[u]*c[ep[i].v];

    }

    if(1-x1<1e-9) return 0;

    a[u]/=1-x1;b[u]/=1-x1;c[u]/=1-x1;

    return 1;

}

int main()

{

    int u,v;

    scanf("%d",&t);

    for(int ca=1;ca<=t;ca++)

    {

        memset(hd,-1,sizeof(hd));kh=0;memset(siz,0,sizeof(siz));

        scanf("%d",&n);

        for(int i=1;i<n;i++)

        {

            scanf("%d%d",&u,&v);

            add(u,v);add(v,u);siz[u]++;siz[v]++;

        }

        for(int i=1;i<=n;i++)

        {

            scanf("%lf%lf",k+i,e+i);

            k[i]/=100;e[i]/=100;

        }

        printf("Case %d: ",ca);

        if(dfs(1,0)&&fabs(1-a[1])>1e-9) printf("%lf\n",c[1]/(1-a[1]));

        else printf("impossible\n");

    }

    return 0;

}
巴特西

hdu4035 Maze 题解

最新文章

热门文章
