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;

}