CF605E Intergalaxy Trips 题解

## CF605E Intergalaxy Trips 题解 **期望好题（确信）** 总之就是，期望做得太少，人太菜，一上午做不出来。 #### 题意不再赘述啦 [CF605E Intergalaxy Trips](https://www.luogu.com.cn/problem/CF605E) #### 朴素分析 首先有个思路，如果我们设 $f_i$ 为 $i\to n$ 的期望耗时，那么当我们转移时，我们**一定不会找比当前点更劣的点转移**。因为那样就是跑个自环也比跑那个劣的点划算，所以转移的时候只考虑比当前点优的点即可。 问题是自己不知道，别的也不知道，怎么判断？这个就要看转移方程了。 #### 状态转移 因为会选择最优策略，所以到了某个点，采取某个状态的唯一可能就是**比自己优的状态取不到了**，这个东西是可以描述出来的。而且如果所有状态都取不到那就自环，这是最劣的转移，不过也要考虑。于是我们的转移方程： $$ f_i=\sum_{j}^{f_j<f_i}p_{i,j}f_j\prod_k^{f_k<f_j}(1-p_{i,k})+f_i\prod_{j}^{f_j<f_i}(1-p_{i,j})+1 $$ 移项然后除一下可以得到： $$ f_i=\frac{\sum_{j}^{f_j<f_i}p_{i,j}f_j\prod_k^{f_k<f_j}(1-p_{i,k})+1}{1-\prod_{j}^{f_j<f_i}(1-p_{i,j})} $$ #### 实现思路 首先，对于上式中的更新 $i$ 的 $j$，显然是考虑的越多**值是单调不增的**，不然你也不会用那个点去转移。然后注意，**一个点是不可能比将它转移的点更优**的，因为要多走一步。 这说明了什么？当一个点是所有已知状态中最小的，那么它就不会再被别的状态转移了，这个性质很类似 Dijkstra ，所以我们可以每一轮选择最小的那个没有进行过转移的点，将其它没有进行过转移的点更新一下，类似朴素的 $O(n^2)$ 的 Dijkstra ，这样我们就能得到答案。 注意这里“转移”指的是**用当前点去更新别的点的答案**，即对于别的点 $i$ 来说，它相当于公式里面的 $j$。 #### 实现细节 我们可以分别维护每个点的 $f_i,g_i,h_i$，$f_i$ 与上文含义相同，三者关系可表示为： $$ f_i=\frac{g_i}{1-h_i} $$ 而且更有趣的是，当我们**用 $j$ 更新 $i$ 时**（注意不是任意时刻），还没被 $j$ 更新过的 $h_i$ 恰好等于 $\prod_k^{f_k<f_j}(1-p_{i,k})$，也就是每一轮更新我们可以这么写： $g_i+=p_{i,j}f_jh_i$，$h_i*=1-p_{i,j}$，$f_i=\frac{g_i}{1-h_i}$ 要注意转移顺序。 #### 贴代码 ```cpp #include <bits/stdc++.h> #define lint long long #define rint register int using namespace std; inline int read(){ char c;int f=1,res=0; while(c=getchar(),!isdigit(c))if(c=='-')f*=-1; while(isdigit(c))res=res*10+c-'0',c=getchar(); return res*f; } const int N=1e3+5,inf=1e9; double p[N][N],f[N],g[N],h[N]; //最后的f才是答案,其为g/(1-h) int q[N],tot,n;//q实质上是拓扑序排列 bool vis[N];//判断是否在队列里面 inline void upd(){//用队头来更新 int j=q[tot]; for(rint i=1;i<=n;++i){ if(vis[i])continue; g[i]+=f[j]*p[i][j]*h[i]; h[i]*=1-p[i][j]; f[i]=g[i]/(1-h[i]); } } inline void solve(){ for(rint i=1;i<n;++i) f[i]=g[i]=h[i]=1; f[n]=0;h[n]=1; //恰好都是1 vis[n]=true; q[++tot]=n;upd(); while(tot<n){ int id;double v=inf; for(rint i=1;i<=n;++i) if(!vis[i]&&f[i]<v) v=f[i],id=i; vis[id]=true; q[++tot]=id;upd(); } } int main(){ n=read(); if(n==1){return puts("0"),0;} for(rint i=1;i<=n;++i) for(rint j=1;j<=n;++j) p[i][j]=read()/100.0; solve(); printf("%.8lf",f[1]); return 0; } ```