【Ctsc2011】幸福路径

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2306

---

给定一张有向图，每个点有权值，蚂蚁从某个节点出发，初始体力值为$1$，每走一条边$体力值*=p$，每经过一个点会获得幸福值为$点权*体力值$，求最大幸福值。即求

${\sum _{i=0}^{\infty }w[i]*p^{i}}$且${U(i-1,i)=1}$其中${U(A,B)}$表示是否存在A到B这样一条路径。

---

正解是一个叫做倍增Floyed的东西。

其实就是说考虑到步数是可以走无限步的，我们只需要知道一个近似值，而精度要求也还是比较高的，考虑用倍增的方法快速确定精度。
令${f[i][j][k]}$表示从第$i$个点走到第$j$个点，期间走了${2^{k}}$步。

那么可以利用Floyed进行如下转移：
$${f[i][j][k]=max(\forall (f[i][t][k-1]+f[t][j][k-1]*p^{2^{k}}))}$$

注意$k$这一维是可以滚动的。

---

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<vector>

 #include<cstdlib>

 #include<cmath>

 #include<cstring>

 using namespace std;

 #define maxn 110

 #define inf 0x7fffffff

 #define llg long long

 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

 llg n,m,S;

 double p,ans,a[maxn],f[maxn][maxn],g[maxn][maxn],tmp;

 int main()

 {

     yyj("a");

     cin>>n>>m;

     for (llg i=;i<=n;i++) scanf("%lf",&a[i]);

     cin>>S>>p;

     for (llg i=;i<=n;i++)

         for (llg j=;j<=n;j++)

             if (i!=j) f[i][j]=inf*-;

     for (llg i=;i<=m;i++)

     {

         llg x,y;

         scanf("%lld%lld",&x,&y);

         f[x][y]=a[y];

     }

     llg T=;

     double tmp=p;

     while (T--)

     {

         //tmp*=tmp;

         for (llg i=;i<=n;i++)

             for (llg j=;j<=n;j++)

                 if (i!=j) g[i][j]=inf*-;

         for (llg k=;k<=n;k++)

             for (llg i=;i<=n;i++)

                 for (llg j=;j<=n;j++)

                     g[i][j]=max(g[i][j],f[i][k]+f[k][j]*tmp);

         memcpy(f,g,sizeof f);

         tmp*=tmp;

     }

     for (llg i=;i<=n;i++) ans=max(ans,f[S][i]);

     printf("%.1lf\n",ans*p+a[S]);

     return ;

 }