AC（Accepted，即满分的意思）这道题目是我这次CTSC2011（国际信息奥赛中国国家队选拔赛暨精英赛）拿金牌的主要原因，在此写一份解题报告作为纪念，同时也和大家分享一下。

题目简述：
n点m边带点权有向图，起点处体力为1，每走过一边体力乘p（0<p<1），路径幸福指数为各点点权*体力之和，路径可以无限长，求最大幸福指数。
n≤100，m≤1000。要求1s内出解。

算法描述：
最暴力的方式是用Bellman-Ford迭代，也就是每次从所有点往下走一步，不断迭代直到数值小于一个极小值，对答案没有什么影响的时候结束，但是p>=0.999的时候会TLE（超时），而且这不是精确算法。
对于一个固定的环，可以知道如果在里面无限绕圈，结果为一等比数列求和求极限，且推出的式子包含环上绕一圈的收益和环的长度两个参数，所以只要枚举环的长度和起点，求出在此条件下收益最大的环即可。而由于对于每一个点，下一步的最优决策其实是固定的，所以路径必定为走一条链，然后停下或者进入一个环开始死循环，所以只要枚举一条路径，再枚举一个环即可。
为了解决以上问题，可以用DP（动态规划），f[i,j,k]表示从j到k走i步的收益最大路径，则f[i,j,j]就是一个环，可以很方便地解决以上问题，时间复杂度为O(n^2*m)。
至于这个DP怎么做，其实很简单，f[i,j,k]=Sigma{f[i-1,j,l]+w[k]*p^i},其中l为满足存在l->k这条边的点，w为点权。

总结：
这题刚开始想到的是二分答案的思路，进过尝试后发现完全无法通过数学变换得到判定性问题的图论解，由尝试了矩阵快速幂，但是同时存在常数矩阵和系数矩阵的时候按照普通的方式进行矩阵快速幂会使矩阵内的元素变成多项式的形式，虽然解题报告中也有这种方式，但是还是不理解如何做到了，且此方法只能得到近似解。于是开始分析问题的特性，得到了路径形态的猜想，并进行了不是很严格的证明，得到了一个优秀的DP算法。

我的程序（C++）：

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <memory.h>
#include <cstring>
#include <algorithm>
#include <iomanip>

#define Max(a, b)            (a > b ? a : b)

using namespace std;

const int MaxN = 110, MaxM = 1100;

int n, m, S, u[MaxM], v[MaxM];
double p, a[MaxN], f[MaxN][MaxN][MaxN], g[MaxN], Power[MaxN], Ans;

void Init()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%lf",&a[i]);
    scanf("%d%lf", &S, &p);
    for (int i = 1; i <= m; ++i)
        scanf("%d%d", &u[i], &v[i]);
    Power[0] = 1;
    for (int i = 1; i <= n; ++i)
        Power[i] = Power[i-1]*p;
}

int main()
{
    freopen("XXXXXXX", "r", stdin);
    freopen("path.out", "w", stdout);
    Init();
    for (int i = 0, j, k; i <= n; ++i)
        for (j = 1; j <= n; ++j)
            for (k = 1; k <= n; ++k)
                f[i][j][k] = -1E20;
    for (int i = 1; i <= n; ++i)
        g[i] = f[0][i][i] = a[i];
    for (int i = 1, j, k; i <= n; ++i)
        for (j = 1; j <= n; ++j)
            for (k = 1; k <= m; ++k)
                f[i][j][v[k]] = Max(f[i][j][v[k]], f[i-1][j][u[k]]+a[v[k]]*Power[i]);
    for (int i = 1, j; i <= n; ++i)
        for (j = i; j <= n; ++j)
            g[i] = Max(g[i], (f[j][i][i]-a[i]*Power[j])/(1-Power[j]));
    for (int i = 1, j; i <= n; ++i)
        for (j = 0; j <= n; ++j)
            Ans = Max(Ans, f[j][S][i]-a[i]*Power[j]+Power[j]*g[i]);
    cout << setprecision(1) << fixed << Ans << endl;
    return 0;
}



代码不长，主要还是在思维复杂度上，赛场上我用了两个小时来完成本题。
如果有什么不足，还请大家指出。