题意：有一棵树，主人公要从1开始走，逃生，问逃生的期望步数，在1这个点 不可能死也不可能逃生，在别的点有ei的概率逃生，ki的概率死亡并且回到1这个点。
思路：
真的是难推啊，我们定义f数组为在i这个点逃生的期望步数，由于是无向图，我们先从叶子结点考虑，
f[i]=0e[i]+ k[i]f[1] + (1-ei-ki)(f[fa[i]]+1)
对于普通节点
f[i]=0e[i]+k[i]f[1]+(1-ei-ki)/m(f[fa[i]]+1)+zigma((1-ei-ki)/m*(f[child[i]]) 其中m代表i这个点的度数。
把child带进去 求出f的相应式子，将f变为Af[1]+Bf[fa]+C,最后答案是f1，f1的B该项为0，所以就是f[1]=Af[1]+C ,f[1]=C/(1-A) ,当A趋近于1的时候那么就是无解.
代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<string>
#include<math.h>
#include<vector>
#include<queue>
#include<stack>
#include<iostream>
#include<sstream>
#define x first
#define y second
#define lson u<<1
#define rson u<<1|1
#define pb push_back
#define pu pushup
#define mk make_pair
using namespace std;
#define ll long long
#define mod 1000000007
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
const int N=10010;
double dp[N],k[N],ee[N];
double A[N],B[N],C[N];
#define eps 1e-9
int n;
int h[N],idx,e[N*2],ne[N*2];
int d[N];
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool dfs(int u,int fa)
{
int m=d[u];
A[u]=k[u];
B[u]=(1-ee[u]-k[u])/m;
C[u]=1-ee[u]-k[u];
double tmp=1;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(j==fa) continue;
if(!dfs(j,u)) return false;
A[u]+=(1-ee[u]-k[u])/m*A[j];
C[u]+=(1-ee[u]-k[u])/m*C[j];
tmp-=(1-ee[u]-k[u])/m*B[j];
}
if(fabs(tmp)<eps) return false;
A[u]/=tmp;
B[u]/=tmp;
C[u]/=tmp;
return true;
}
int main()
{
int t;
scanf("%d",&t);
int K=0;
while(t--)
{
idx=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
d[i]=0;
for(int i=1;i<=n;i++)
h[i]=-1;
for(int i=0;i<n-1;i++)
{
int a,b;
scanf("%d%d",&a,&b);
d[a]++,d[b]++;
add(a,b),add(b,a);
}
for(int i=1;i<=n;i++)
{
scanf("%lf%lf",&k[i],&ee[i]);
k[i]/=100;
ee[i]/=100;
//cout<<ee[i]<<' '<<
}
printf("Case %d: ",++K);
if(dfs(1,-1) && fabs(A[1]-1)>eps)
printf("%.6lf\n",C[1]/(1-A[1]));
else
puts("impossible");
}
return 0;
}
京公网安备 11010502036488号