【BZOJ2306】幸福路径（动态规划，倍增）

题面

BZOJ

题解

不要求确切的值，只需要逼近

显然可以通过移动\(\infty\)步来达到逼近的效果

考虑每次的一步怎么移动

设\(f[i][j]\)表示走\(i\)步到了\(j\)能够得到的最大权值

\(f[i][v]=max(f[i-1][u])+W[v]*p^i,(u,v)\in G\)

这样的复杂度是\(O(T(n+m))\)，\(T\)是自己设定的步数

但是这样子逼近精度很慢

假设\(p=0.999999\)，大概要\(10^7\)步才能达到目标进度

这样子显然太慢

我们考虑如何优化

既然一步步走很慢，那么我们考虑倍增来走

首先预处理以下两个点之间的连通性

设\(g[i][j][k]\)表示走了\(2^k\)步后是否能从\(i\)到\(j\)

那么，\(f[i][j]\)表示走了\(2^i\)步到达\(j\)能够拿到的最大权值

这样子每次随意枚举两个点\(i,j\)来转移，发现有些东西没法记录

比如枚举两个点，但是不能保证这两个点之间的最优路径是拼接在一起的

所以我们加一维\(f[i][j][l]\)表示从\(i\)到\(j\)走了\(2^l\)步拿到的最优权值

枚举一个中间点\(k\)

\(f[i][j][l]=max(f[i][k][l-1]+p^{2^{l-1}}f[k][j][l-1])\)

这样子的复杂度就是\(O(n^3log10^7)\)了

其实\(g\)也可以不用预处理是否联通，直接把不连通的距离设为\(-inf\)就行了

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

#define MAX 111

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

struct Line{int v,next;}e[MAX<<4];

int h[MAX],cnt=1;

inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;}

int n,m,S;

double f[30][MAX][MAX];

double W[MAX],p,Ans;

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;++i)scanf("%lf",&W[i]);

	scanf("%d",&S);scanf("%lf",&p);

    memset(f,0xfe,sizeof(f));

	for(int i=1;i<=n;++i)f[0][i][i]=0;

	for(int i=1;i<=m;++i)

	{

		int u=read(),v=read();

		f[0][u][v]=W[v]*p;

	}

	for(int l=1;l<30;++l,p*=p)

		for(int k=1;k<=n;++k)

			for(int i=1;i<=n;++i)

				for(int j=1;j<=n;++j)

					f[l][i][j]=max(f[l][i][j],f[l-1][i][k]+p*f[l-1][k][j]);

	for(int i=1;i<=n;++i)Ans=max(Ans,f[29][S][i]);

	printf("%.1lf\n",Ans+W[S]);

	return 0;

}