CF605E Intergalaxy Trips 题解

CF605E Intergalaxy Trips 题解

期望好题（确信）

总之就是，期望做得太少，人太菜，一上午做不出来。

题意不再赘述啦

CF605E Intergalaxy Trips

朴素分析

首先有个思路，如果我们设 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}

要注意转移顺序。

贴代码

#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;
}