转移式形如 \(\displaystyle f_i = \sum_{f_i > f_j} g(i, j) f_j + \sum_{f_i < f_j} h(i, j) \boldsymbol{f_i}\)。
考虑初始化所有 \(f_i\) 为正无穷，化一下式子后发现 \(f_j > f_i\) 时仅仅个数而非具体值时被在意的，则当更新 \(f_j < f_i\) 时能出现额外的、从第二个式子变为第一个式子而产生的贡献。因此按 \(f_i\) 的大小排序并动态处理。每次取出最优的 \(f_i\) 更新其它点，容易发现这样无后效性。
P4745 [CERC2017]Gambling Guide
给定一张无向图，一个人从 \(1\) 出发，站在每个点时每单位时间以均等概率开放一条出边，人可以选择走过这条边或等下一单位时间。求最优策略下到达 \(n\) 的期望时间。
\(n, m \leq 3 \cdot 10^5\)
套路性地设从 \(i\) 到 \(n\) 最佳方案的期望为 \(f_i\)，只考虑一次的选择。如果走过去期望小于留下来，显然该走；不然显然该留。
注意到用 \(f_v < f_u\) 迭代更新 \(u\) 时只会让答案更优，尝试寻找无后效性的迭代方式，则能保证复杂度，否则暴力计算复杂度乘一个 \(n\)。
尝试从小到大计算，则当处理完前 \(i\) 大的期望值时，当前最小的 \(f_u\) 一定是所求第 \(i+1\) 小。
为什么？容易发现此时 \(f_u\) 已经被计算完毕，且其它不在前 \(i\) 大的 \(f_v\) 一定大于它的准确值，从而大于现在的 \(f_u\)。
可以直接迭代 \(n\) 轮每次找最小值更新，可以跑一个 dij 优化每轮找的过程。其实 dij 不也是这样，贪心找全局最小值，使计算一个点对其它点的贡献时它本身已经被计算完毕。
这里依赖了什么呢？好像只有迭代一轮能使答案能优，以及可以快速算把 \(v\) 对 \(u\) 的贡献从一类放到另一类时 \(f_u\) 的变化量，后者满足可减性的式子都能这样干。
其实说完这题后这类题感觉都差不多了，但是做完下一题我才真正理解直接找到全局最小值的正确性。
#include <bits/stdc++.h>
using namespace std;
const int M = 3e6 + 5;
vector<int> e[M];
priority_queue<pair<double, int> > q;
double f[M], sm[M]; int n, m, cnt[M];
bool vis[M];
void dij() {
q.push({0, n});
while (!q.empty()) {
int u = q.top().second; q.pop();
if (vis[u]) continue; vis[u] = 1;
for (auto v : e[u]) {
if (!vis[v]) {
++cnt[v], sm[v] += f[u];
f[v] = (e[v].size() + sm[v]) / cnt[v];
q.push({-f[v], v});
}
}
}
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v; scanf("%d %d", &u, &v);
e[u].push_back(v), e[v].push_back(u);
}
dij(); printf("%.6lf\n", f[1]);
}
咦，最短路是不是也是这样的（
CF605E Intergalaxy Trips
给定一张完全图，\(i \to j\) 的边每天以 \(p_{i, j}\) 的概率出现。站在 \(i\)，每天可以走过一条存在的边或什么都不做。求最优策略下从 \(1\) 走到 \(n\) 的天数的期望。
\(n \leq 300\)
仍然采用与上题一样的设状态法。
显然每天要去期望最小的能到达的点，如果期望最小的点大于当前点则不动。
采用与上一题一样的迭代就行了。从优到劣迭代，即按 \(f\) 从大到小迭代。
分子上的求和用了分母的结果以快速求出，感觉这里挺厉害。不过不能快速求不影响这样能做。
#include <bits/stdc++.h>
using namespace std;
const int M = 1005;
double f[M], g[M], h[M];
int n; double p[M][M];
bool vis[M];
void upd(int j) {
vis[j] = 1;
for (int i = 1; i <= n; i++) if (!vis[i]) {
g[i] += p[i][j] * f[j] * h[i], h[i] *= (1 - p[i][j]);
f[i] = g[i] / (1 - h[i]);
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
scanf("%lf", &p[i][j]), p[i][j] /= 100;
for (int i = 1; i <= n; i++)
f[i] = g[i] = h[i] = 1;
f[n] = g[n] = 0; upd(n);
for (int i = 1; i < n; i++) {
int t = 0;
for (int j = 1; j <= n; j++)
if (!vis[j] && (f[j] < f[t] || (!t)))
t = j;
upd(t);
}
printf ("%.11lf\n", f[1]);
}
在学校里登 cnblogs 太麻烦了 /tuu 终于又感到了 Luogu Blog 的温暖。