Cptraser/ 十二月 1, 2018/ 2018.12/ 0 comments

题面传送门
由于概率的递减,可以考虑有限次的枚举,然后倍增Floyd转移即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const double eps=1e-12,INF=1e9;

int N,M,S,x,y,Cnt;
double Ans,p,A[105],F[105][105][105];

int main()
{
    scanf("%d%d",&N,&M); for(int i=1;i<=N;++i)scanf("%lf",&A[i]);
    for(int i=0;i<=100;i++)for(int j=1;j<=N;j++)for(int k=1;k<=N;k++)F[i][j][k]=-INF;
    for(int i=1;i<=N;i++)F[0][i][i]=0;
    scanf("%d%lf",&S,&p);for(int i=1;i<=M;++i)scanf("%d%d",&x,&y),F[0][x][y]=p*A[y];
    for(Cnt=1;p>eps;++Cnt,p*=p){
        for(int k=1;k<=N;k++)
            for(int i=1;i<=N;i++)
                for(int j=1;j<=N;j++){
                    F[Cnt][i][j]=max(F[Cnt][i][j],F[Cnt-1][i][k]+F[Cnt-1][k][j]*p);
                }
    }
    for(int i=1;i<=N;i++)Ans=max(Ans,F[Cnt-1][S][i]);
    printf("%.1f",Ans+A[S]);
    return 0;
}
Share this Post

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*