這是一道可以當作板子的極簡記憶化搜索?

?

建立a?是鄰接表，其中?a[x]?存儲從節點 x 出發能到達的所有節點。

b[x]?記錄從節點 x 出發的所有邊的權重之和。根據數學原理，我們很容易發現，一個根（起點）的期望，等于他所有子的期望加上邊權和，除邊

?

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, x, y, z;
vector<vector<int>> a(N); //鄰接表
double b[N]; //記錄從節點 x 出發的所有邊的權重之和。

double dfs(int x) {
? ? if (x == n) return 0.0; //到達終點，期望為0

? ? double o = 0.0;
? ? int p = a[x].size();
? ? for (auto i : a[x]) {//所有子的期望和
? ? ? ? o += dfs(i);
? ? }
? ? o += b[x];//加上邊權和
? ? return o / p;//期望
}

int main() {
? ? cin >> n >> m;
? ? for (int i = 0; i < m; ++i) {
? ? ? ? cin >> x >> y >> z;
? ? ? ? a[x].push_back(y);
? ? ? ? b[x] += z;
? ? }
? ? double o = dfs(1);
? ? printf("%.2lf\n", o);?
? ? return 0;
}

這樣寫出來，思路是對的，但是在多條路徑下，我們明顯可以發現，每個子節點都會計算很多次，所以我們使用記憶化來優化；

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, x, y, z;
vector<vector<int>> a(N);?
double b[N];?
double memo[N];? //儲存
bool vis[N]; //判斷是否被計算過

double dfs(int x) {
?? ?if (vis[x]) return memo[x];//如果計算了，直接返回結果
? ? if (x == n) return 0.0;?
? ? vis[x] = true;
? ? double o = 0.0;
? ? int p = a[x].size();
? ? for (auto i : a[x]) {
? ? ? ? o += dfs(i);
? ? }
? ? if (p == 0) return 0.0; ?
? ? o += b[x];
? ? return memo[x]=o / p;//返回時給memo記錄
}

int main() {
? ? cin >> n >> m;
? ? for (int i = 0; i < m; ++i) {
? ? ? ? cin >> x >> y >> z;
? ? ? ? a[x].push_back(y);
? ? ? ? b[x] += z;
? ? }
? ? memset(vis, false, sizeof(vis));//初始化
? ? double o = dfs(1);
? ? printf("%.2lf\n", o);?
? ? return 0;
}