2 条题解
-
0
#include<bits/stdc++.h> using namespace std; const double eps=1e-9; const int N=11100,M=21100; struct edge{int x,y,pre;}a[M];int alen,last[N],out[N]; void add(int x,int y){alen++;a[alen]=edge{x,y,last[x]};last[x]=alen;out[x]++;} double k[N],e[N],A[N],B[N],C[N];bool dfs(int x,int fa) {A[x]=k[x];B[x]=(1-k[x]-e[x])/out[x];C[x]=1-k[x]-e[x];double tmp=0; for(int i=last[x];i;i=a[i].pre) {int y=a[i].y;if(y!=fa) {if(dfs(y,fa)==false)return false; A[x]+=(1-k[x]-e[x])/out[x]*A[y];C[x]+=(1-k[x]-e[x])/out[x]*C[y];tmp+=(1-k[x]-e[x])/out[x]*B[y];}} if(fabs(tmp-1)<eps)return false;A[x]/=(1-tmp);B[x]/=(1-tmp);C[x]/=(1-tmp);return true;} int main() {int T,n;scanf("%d",&T); for(int ti=1;ti<=T;ti++) {scanf("%d",&n);alen=0;memset(last,0,sizeof(last));memset(out,0,sizeof(out)); for(int i=1;i<n;i++){int x,y;scanf("%d%d",&x,&y);add(x,y);add(y,x);} for(int i=1;i<=n;i++){scanf("%lf%lf",&k[i],&e[i]);k[i]/=100;e[i]/=100;} printf("Case %d: ",ti);if(dfs(1,0)==true&&fabs(1-A[1])>eps)printf("%.6lf\n",C[1]/(1-A[1])); else printf("impossible\n");}return 0;}设 E[i]表示在结点i处，要走出迷宫所要走的边数的期望。E[1]即为所求。
叶子结点： E[i] = ki*E[1] + ei*0 + (1-ki-ei)*(E[father[i]] + 1); = ki*E[1] + (1-ki-ei)*E[father[i]] + (1-ki-ei); 非叶子结点：（m为与结点相连的边数） E[i] = ki*E[1] + ei*0 + (1-ki-ei)/m*( E[father[i]]+1 + ∑( E[child[i]]+1 ) ); = ki*E[1] + (1-ki-ei)/m*E[father[i]] + (1-ki-ei)/m*∑(E[child[i]]) + (1-ki-ei); 设对每个结点：E[i] = Ai*E[1] + Bi*E[father[i]] + Ci; 对于非叶子结点i，设j为i的孩子结点，则 ∑(E[child[i]]) = ∑E[j] = ∑(Aj*E[1] + Bj*E[father[j]] + Cj) = ∑(Aj*E[1] + Bj*E[i] + Cj) 带入上面的式子得 (1 - (1-ki-ei)/m*∑Bj)*E[i] = (ki+(1-ki-ei)/m*∑Aj)*E[1] + (1-ki-ei)/m*E[father[i]] + (1-ki-ei) + ( (1-ki-ei)/m )*∑Cj; 由此可得 Ai = (ki+(1-ki-ei)/m*∑Aj) / (1 - (1-ki-ei)/m*∑Bj); Bi = (1-ki-ei)/m / (1 - (1-ki-ei)/m*∑Bj); Ci = ( (1-ki-ei) + (1-ki-ei)/m*∑Cj ) / (1 - (1-ki-ei)/m*∑Bj); 对于叶子结点 Ai = ki; Bi = 1 - ki - ei; Ci = 1 - ki - ei; 从叶子结点开始，直到算出 A1,B1,C1; E[1] = A1*E[1] + B1*0 + C1; 所以 E[1] = C1 / (1 - A1); 若 A1趋近于1则无解... -
0
huangzheng
LV 6
@ 2025-10-8 16:50:46
#include<bits/stdc++.h> using namespace std; const double eps=1e-9; const int N=11100,M=21100; struct edge{int x,y,pre;}a[M];int alen,last[N],out[N]; void add(int x,int y){alen++;a[alen]=edge{x,y,last[x]};last[x]=alen;out[x]++;} double k[N],e[N],A[N],B[N],C[N]; bool dfs(int x,int fa) { A[x]=k[x]; B[x]=(1-k[x]-e[x])/out[x]; C[x]=1-k[x]-e[x]; double tmp=0; for(int i=last[x];i;i=a[i].pre) { int y=a[i].y; if(y!=fa) { if(dfs(y,x)==False)return False; A[x]+=(1-k[x]-e[x])/out[x] *A[y]; C[x]+=(1-k[x]-e[x])/out[x] *C[y]; tmp +=(1-k[x]-e[x])/out[x] *B[y]; } } if(fabs(tmp-1)<eps)return False; A[x]/=(1-tmp); B[x]/=(1-tmp); C[x]/=(1-tmp); return True; } int main() { int T,n;scanf("%d",&T); for(int ti=1;ti<=T;ti++) { scanf("%d",&n); alen=0;memset(last,0,sizeof(last));memset(out,0,sizeof(out)); for(int i=1;i<n;i++) { int x,y;scanf("%d%d",&x,&y);add(x,y);add(y,x); } for(int i=1;i<=n;i++) { scanf("%lf%lf",&k[i],&e[i]); k[i]/=100;e[i]/=100; } printf("Case %d: ",ti); if(dfs(1,0)==True&&fabs(1-A[1])>eps) printf("%.6lf\n",C[1]/(1-A[1])); else printf("impossible\n"); } return 0; } /* 设 E[i]表示在结点i处，要走出迷宫所要走的边数的期望。E[1]即为所求。 叶子结点： E[i] = ki*E[1] + ei*0 + (1-ki-ei)*(E[father[i]] + 1); = ki*E[1] + (1-ki-ei)*E[father[i]] + (1-ki-ei); 非叶子结点：（m为与结点相连的边数） E[i] = ki*E[1] + ei*0 + (1-ki-ei)/m*( E[father[i]]+1 + ∑( E[child[i]]+1 ) ); = ki*E[1] + (1-ki-ei)/m*E[father[i]] + (1-ki-ei)/m*∑(E[child[i]]) + (1-ki-ei); 设对每个结点：E[i] = Ai*E[1] + Bi*E[father[i]] + Ci; 对于非叶子结点i，设j为i的孩子结点，则 ∑(E[child[i]]) = ∑E[j] = ∑(Aj*E[1] + Bj*E[father[j]] + Cj) = ∑(Aj*E[1] + Bj*E[i] + Cj) 带入上面的式子得 (1 - (1-ki-ei)/m*∑Bj)*E[i] = (ki+(1-ki-ei)/m*∑Aj)*E[1] + (1-ki-ei)/m*E[father[i]] + (1-ki-ei) + (1-ki-ei)/m*∑Cj; 由此可得 Ai = (ki+(1-ki-ei)/m*∑Aj) / (1 - (1-ki-ei)/m*∑Bj); Bi = (1-ki-ei)/m / (1 - (1-ki-ei)/m*∑Bj); Ci = ( (1-ki-ei)+(1-ki-ei)/m*∑Cj ) / (1 - (1-ki-ei)/m*∑Bj); 对于叶子结点 Ai = ki; Bi = 1 - ki - ei; Ci = 1 - ki - ei; 从叶子结点开始，直到算出 A1,B1,C1; E[1] = A1*E[1] + B1*0 + C1; 所以 E[1] = C1 / (1 - A1); 若 A1趋近于1则无解... */
<br />
<br />
<br />
<br />
- 1