bzoj2306 [Ctsc2011]幸福路径 倍增 Floyd

题目传送门

https://lydsy.com/JudgeOnline/problem.php?id=2306

题解

倍增 Floyd。

令 \(f[i][j][k]\) 表示走了 \(2^i\) 步，从 \(j\) 到 \(k\) 的距离最大值。

然后转移就是 \(f[i][j][k] = \max\limits_{l=1}^n f[i-1][j][l] + p \cdot f[i-1][l][k]\)。

---

另外要每一个点建立一个长度为 \(0\) 的自环，用来统计总的最大值。

#include<bits/stdc++.h>

#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define fi first
#define se second
#define pb push_back

template<typename A, typename B> inline char smax(A &a, const B &b) {return a < b ? a = b, 1 : 0;}
template<typename A, typename B> inline char smin(A &a, const B &b) {return b < a ? a = b, 1 : 0;}

typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii;

template<typename I> inline void read(I &x) {
    int f = 0, c;
    while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;
    x = c & 15;
    while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);
    f ? x = -x : 0;
}

const int N = 100 + 7;
const double INF = 1e18;

int n, m, st;
double p;
double a[N], f[N][N][N];

inline void work() {
    for (int i = 1; i <= 30; ++i, p = p * p)
        for (int j = 1; j <= n; ++j)
            for (int k = 1; k <= n; ++k)
                for (int l = 1; l <= n; ++l) smax(f[i][j][k], f[i - 1][j][l] + p * f[i - 1][l][k]);
//  for (int i = 0; i <= 30; ++i)
//      for (int j = 1; j <= n; ++j)
//          for (int k = 1; k <= n; ++k) dbg("f[%d][%d][%d] = %.10lf\n", i, j, k, f[i][j][k]);
    double ans = 0;
    for (int i = 1; i <= n; ++i) smax(ans, f[30][st][i]);
    ans += a[st];
    printf("%.1lf\n", ans);
}

inline void init() {
    read(n), read(m);
    for (int i = 1; i <= n; ++i) scanf("%lf", &a[i]);
    for (int i = 0; i <= 30; ++i)
        for (int j = 1; j <= n; ++j) {
            for (int k = 1; k <= n; ++k) f[i][j][k] = -INF;
            f[i][j][j] = 0;
        }
    scanf("%d%lf", &st, &p);
    int x, y;
    for (int i = 1; i <= m; ++i) read(x), read(y), f[0][x][y] = p * a[y];
}

int main() {
#ifdef hzhkk
    freopen("hkk.in", "r", stdin);
#endif
    init();
    work();
    fclose(stdin), fclose(stdout);
    return 0;
}