首页 > 代码库 > bzoj3640: JC的小苹果
bzoj3640: JC的小苹果
Description
让我们继续JC和DZY的故事。
“你是我的小丫小苹果，怎么爱你都不嫌多！”
“点亮我生命的火，火火火火火！”
话说JC历经艰辛来到了城市B，但是由于他的疏忽DZY偷走了他的小苹果！没有小苹果怎么听歌！他发现邪恶的DZY把他的小苹果藏在了一个迷宫里。JC在经历了之前的战斗后他还剩下hp点血。开始JC在1号点，他的小苹果在N号点。DZY在一些点里放了怪兽。当JC每次遇到位置在i的怪兽时他会损失Ai点血。当JC的血小于等于0时他就会被自动弹出迷宫并且再也无法进入。
但是JC迷路了，他每次只能从当前所在点出发等概率的选择一条道路走。所有道路都是双向的，一共有m条，怪兽无法被杀死。现在JC想知道他找到他的小苹果的概率。
P.S.大家都知道这个系列是提高组模拟赛，所以这是一道送分题balabala
Input
第一行三个整数表示n，m，hp。接下来一行整数，第i个表示jc到第i个点要损失的血量。保证第1个和n个数为0。接下来m行每行两个整数a，b表示ab间有一条无向边。
Output
仅一行，表示JC找到他的小苹果的期望概率，保留八位小数。
将图按hp剩余量分层，用f[a][w]表示hp剩余a，当前在点w到达终点的概率
递推式只与当前层和hp更小的层有关，预处理对与当前层相关的部分构成的递推矩阵求逆，于是可以O(n^2)转移一层
时间复杂度O(n^3+n^2*hp)
#include<bits/stdc++.h>typedef double ld;int n,m,hp,vs[155];std::vector<int>es[155];ld f[10007][155],xs[155][155],ys[155],zs[155][155];void ae(int a,int b){ if(a==n)return; ++xs[a][a]; if(vs[b])es[a].push_back(b); else --xs[a][b];}int main(){ scanf("%d%d%d",&n,&m,&hp); for(int i=1;i<=n;++i)scanf("%d",vs+i),zs[i][i]=1; for(int i=0,a,b;i<m;++i){ scanf("%d%d",&a,&b); ae(a,b);if(a!=b)ae(b,a); } xs[n][n]=1; for(int i=1;i<=n;++i){ int w=i; for(int j=i+1;j<=n;++j)if(fabs(xs[j][i])>fabs(xs[w][i]))w=j; if(w!=i) for(int j=1;j<=n;++j){ std::swap(xs[i][j],xs[w][j]); std::swap(zs[i][j],zs[w][j]); } ld a=xs[i][i]; for(int j=1;j<=n;++j){ xs[i][j]/=a; zs[i][j]/=a; } for(int j=1;j<=n;++j)if(j!=i){ a=xs[j][i]; for(int k=1;k<=n;++k){ xs[j][k]-=xs[i][k]*a; zs[j][k]-=zs[i][k]*a; } } } for(int t=1;t<=hp;++t){ for(int i=1;i<n;++i){ ys[i]=0; for(int j=0;j<es[i].size();++j){ int u=es[i][j]; if(vs[u]<t)ys[i]+=f[t-vs[u]][u]; } } ys[n]=1; for(int i=1;i<=n;++i){ ld s=0; for(int j=1;j<=n;++j)s+=zs[i][j]*ys[j]; f[t][i]=s; } } printf("%.8f\n",f[hp][1]); return 0;}
bzoj3640: JC的小苹果
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。