题解 P4308 【[CTSC2011]幸福路径】

shadowice1984

2018-07-23 16:05:34

Solution

倍增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]&&lt[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]&&lt1[k][j]);p*=p; } for(int i=1;i<=n;i++)res=max(res,mp[st][i]);printf("%.1Lf",res+w[st]);return 0;//拜拜程序~ } ````