首页 > 代码库 > 【Ctsc2011】幸福路径
【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$这一维是可以滚动的。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 using namespace std; 9 #define maxn 11010 #define inf 0x7fffffff11 #define llg long long 12 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);13 llg n,m,S;14 double p,ans,a[maxn],f[maxn][maxn],g[maxn][maxn],tmp;15 int main()16 {17 yyj("a");18 cin>>n>>m;19 for (llg i=1;i<=n;i++) scanf("%lf",&a[i]);20 cin>>S>>p;21 for (llg i=1;i<=n;i++)22 for (llg j=1;j<=n;j++)23 if (i!=j) f[i][j]=inf*-1;24 for (llg i=1;i<=m;i++)25 {26 llg x,y;27 scanf("%lld%lld",&x,&y);28 f[x][y]=a[y];29 }30 llg T=50;31 double tmp=p;32 while (T--)33 {34 //tmp*=tmp;35 for (llg i=1;i<=n;i++)36 for (llg j=1;j<=n;j++)37 if (i!=j) g[i][j]=inf*-1;38 for (llg k=1;k<=n;k++)39 for (llg i=1;i<=n;i++)40 for (llg j=1;j<=n;j++)41 g[i][j]=max(g[i][j],f[i][k]+f[k][j]*tmp);42 memcpy(f,g,sizeof f);43 tmp*=tmp;44 }45 for (llg i=1;i<=n;i++) ans=max(ans,f[S][i]);46 printf("%.1lf\n",ans*p+a[S]); 47 return 0;48 }
【Ctsc2011】幸福路径
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。