题解 P4308 【[CTSC2011]幸福路径】
shadowice1984
2018-07-23 16:05:34
倍增floyd大法好……
我们设$Dp_{i,j,k}$表示从i出发到j长度为$2^k$的简单路径的最大H值和
那么转移方程就是,我们枚举i和j中间的接口t进行转移
## $Dp_{i,j,k}=max_{t=1}^{n}(Dp_{i,t,k-1}+P^{2^{k-1}}Dp_{t,j,k-1})$
边界条件
## $Dp_{i,j,0}=Pw_{j}$
另外一点需要注意的是我们还需要通过倍增floyd传递闭包求出i到t,t到j之间是否存在一条长度为$2^{k-1}$的有向路径,从而判定刚才的dp方程是否可以完成转移
然后问题来了,我们这样下去循环是会无限进行下去的,什么时候终止循环呢?
# 醒醒,这道题是输出实数!
这意味这我们无需求出精确值,只需要求出一(和)个(std)足(错)够(的)精(一)确(样)的解就可以了
因此,我们只需要当$P^{2^{k-1}}$小于eps的时候中止循环就可以了……
上代码~
```C
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
using namespace std;const int N=110;typedef long double ld;const ld eps=1e-10;
ld p;ld w[N];ld mp[N][N];ld tr1[N][N];bool lt[N][N];bool lt1[N][N];int n;int m;int st;ld res=0;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%Lf",&w[i]);
scanf("%d",&st);scanf("%Lf",&p);
for(int i=1,u,v;i<=m;i++){scanf("%d%d",&u,&v);mp[u][v]+=w[v]*p;lt[u][v]=true;}
while(p>eps)
{
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)tr1[i][j]=mp[i][j];
for(int i=1;i<=n;i++)//传递闭包
for(int k=1;k<=n;k++)
for(int j=1;j<=n;j++)
if(lt[i][k]&<[k][j])mp[i][j]=max(mp[i][j],tr1[i][k]+p*tr1[k][j]);
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)lt1[i][j]=lt[i][j];
for(int i=1;i<=n;i++)//dp
for(int k=1;k<=n;k++)
for(int j=1;j<=n;j++)lt[i][j]=lt[i][j]||(lt1[i][k]&<1[k][j]);p*=p;
}
for(int i=1;i<=n;i++)res=max(res,mp[st][i]);printf("%.1Lf",res+w[st]);return 0;//拜拜程序~
}
````