自动搬运

查看原文

来自洛谷，原作者为

	hsfzLZH1 我永远喜欢珂朵莉

搬运于2025-08-24 21:58:48，当前版本为作者最后更新于2020-02-20 22:01:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

首先给出 性质： 若答案路径的长度有限，则必不经过重复的点；若答案路径的长度无限，则必为先走一条有限的路径（长度可能为 $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;
}