分开算男女的期望，因为是等概率出现各个景点，并且是等概率选择分支景点，所以记忆化搜索满意度和再除以n就行了。
#include <bits/stdc++.h> using namespace std; int n,m,k; const int N=1e5+10; int ci[N],h[N][3]; double f[105][500][3]; typedef pair<int,int> pp; vector<pp> g[N]; double dfs(int u,int K,int id) { if(f[u][K][id]) return f[u][K][id]; int size=0; double sum=0; for(auto it:g[u]){ int v=it.first,w=it.second; if(K>=w+ci[v]) size++,sum+=dfs(v,K-w-ci[v],id); } if(size) sum/=size; sum+=1.0*h[u][id]; return f[u][K][id]=sum; } void solve() { scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++){ scanf("%d%d%d",&ci[i],&h[i][0],&h[i][1]); } for(int i=1;i<=m;i++){ int x,y,t; scanf("%d%d%d",&x,&y,&t); g[x].push_back({y,t}); g[y].push_back({x,t}); } double res1=0,res2=0; for(int i=1;i<=n;i++){ if(k>=ci[i]){ res1+=dfs(i,k-ci[i],0); res2+=dfs(i,k-ci[i],1); } } printf("%.5lf %.5lf\n",res1/(1.0*n),res2/(1.0*n)); } signed main() { solve(); }