这篇文章上次修改于 464 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

本文共 1336 个字，阅读时长 ≈ 4 分钟

P4308 [CTSC2011] 幸福路径

题目链接

题意

给定一个 N 个点 M 条边的有向图，每个点有点权，初始体力值为1，每经过一条边体力值会变为原来的 p 倍，定义到达一个点时获得的幸福度为到达这个点时的体力值乘以这个点的点权。从给定的起点出发，不限步数，求可能得到的最大幸福度。

思路

和此题类似，考虑到直接枚举步数时间复杂度会爆炸，想想如何优化，可以用倍增优化枚举过程。我们设 $f[t][i][j]$ 表示从 i 跳到 j，跳了 $2^t$ 步时可能得到的最大幸福度。转移自然是利用 $2^{t-1}\times 2=2^t$ 这个性质转移，方程为 $f[t][i][j]=\max(f[t][i][j],f[t-1][i][k]+f[t-1][k][j]\times p)$，为什么后面要乘以 p 呢，因为我们从 k 向 j 跳时，比之前数组中记录的多了一步，所以体力值就变成之前数组中记录的值所对应的体力值的 p 倍。连边时将 $f[0][i][j]$ 初始化为 $p*a[j]$ 即可。

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return x*f;
}
const int N=102,inf=1<<30;
int n,m,s;
double p;
double a[N];
double f[33][N][N];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) scanf("%lf",&a[i]);
    scanf("%d%lf",&s,&p);
    int u,v;
        //初始化
    for(int k=0;k<32;++k)
        for(int i=0;i<=n;++i)
            for(int j=0;j<=n;++j)
                if(i!=j) f[k][i][j]=-inf;
    for(int i=1;i<=m;++i){
        scanf("%d%d",&u,&v);
                //加边时将f[0][u][v]初始化为体力值乘以终点点权
        f[0][u][v]=p*a[v];
    }
        //比平常的floyd多了一个倍增枚举步数
    for(int t=1;t<32;++t){
        for(int k=1;k<=n;++k)
            for(int i=1;i<=n;++i)
                for(int j=1;j<=n;++j)
                    f[t][i][j]=max(f[t][i][j],f[t-1][i][k]+f[t-1][k][j]*p);
        //更改下一步的体力值
                p*=p;
                //如果p已经微乎其微就直接跳出
        if(p<=(1e-9)) break;
    }
    double ans=0.0;
    for(int t=1;t<32;++t)
        for(int i=1;i<=n;++i)
            ans=max(ans,f[t][s][i]);
        //别忘了加上起点的点权
    printf("%.1lf",ans+a[s]);
    return 0;
}