题解 P4308 【[CTSC2011]幸福路径】

· · 题解

至今为止，本题的所有题解都利用了本题的一个特性：答案在精度范围内即可。但是，如果去掉这个特性，比如要求输出为分数的形式，那么就要求出 精确解 ，这时有没有优秀的解法呢？本篇题解给出的就是这样的解法。

首先给出 性质： 若答案路径的长度有限，则必不经过重复的点；若答案路径的长度无限，则必为先走一条有限的路径（长度可能为 0 ），然后不停走一个环，有限路径和该环中都没有重复的点。

证明： 因为所有点的权值都是正的，所以多走一步肯定有收益，能走的时候肯定会走。若从一个点开始已经走了一个环，那接下来肯定会继续走经过这个点的环，若经过的是和之前不同的环，那我们从一开始就不停地走这个环，一定更优。在我们从起点走到无限走的单环的路径上，如果存在重复的点，那么就存在环，要么不走这个环，要么一直走这个环，其中一定有比当前方案优的。

根据性质，我们有这样的解法：定义 f[i][j][k] 表示从 i 到 j ，经过 k 个点（可以重复），不包括结点 i 所得的最大收益。之前指出，最优路径中没有重复的点，所以需要计算的 k\le n 。我们知道 f[i][i][0]=0 ，状态转移方程为 f[i][v][k]=\max\{f[i][u][k-1]+w[v]\times \rho^k \} （若从 u 到 v 有边）。定义 c[i] 表示从 i 开始不停走环的最大收益（若无环则值为 0 ），由等比数列求和公式有 c[i]=\max\{\frac {f[i][i][k]} {1-\rho^k}\} 。

最后，我们枚举有限路径的终点，枚举走到该终点的步数，最后加上最优的环的价值，就可求得答案。

预处理 \rho 的幂的值，计算 f 数组的时间复杂度为 O(n^2m) ，计算 c 数组的时间复杂度为 O(nm) ，根据两数组求答案的时间复杂度为 O(n^2) 。空间复杂度为 O(n^3) 。

参考代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=110;
const double inf=2e9;
int n,m,v0,x,y,g[maxn][maxn];
double w[maxn],rho,f[maxn][maxn][maxn],c[maxn],pww[maxn],ans; 
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lf",w+i);
    scanf("%d%lf",&v0,&rho);
    pww[0]=1.0;for(int i=1;i<=n+1;i++)pww[i]=pww[i-1]*rho;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=0;k<=n;k++)f[i][j][k]=-inf;
    for(int i=1;i<=n;i++)f[i][i][0]=0; 
    while(m--)scanf("%d%d",&x,&y),g[x][y]=1;
    for(int k=1;k<=n;k++)for(int j=1;j<=n;j++)for(int t=1;t<=n;t++)if(g[j][t])
    for(int i=1;i<=n;i++)if(f[i][j][k-1]>=-1e-6)f[i][t][k]=max(f[i][t][k],f[i][j][k-1]+pww[k]*w[t]);
    for(int i=1;i<=n;i++)for(int k=1;k<=n;k++)if(f[i][i][k]>=-1e-6)c[i]=max(c[i],f[i][i][k]/(1.0-pww[k]));
    for(int i=1;i<=n;i++)for(int k=0;k<=n;k++)ans=max(ans,w[v0]+f[v0][i][k]+c[i]*pww[k]);
    printf("%.1lf\n",ans);
    return 0;
}