P4316 绿豆蛙的归宿【概率DP+拓扑】

传送门 这是一个DAG模型的DP 既然是个DAG，那么我们可以“倒过来”想 具体来讲，我们反向连边，进行一遍拓扑排序，在拓扑排序的时候进行期望dp的转移 对一条有向边，我们假定有$u->v$ 那么有$dp[u]=(\frac{1}{degree(u)})\ast \sum f[y]+w[x->y]$ 其中$degree(u)$表示u点的度（结合一下上面给出的式子你就懂了） 仔细观察题目其实你会发现,$\frac{1}{degree(u)}$ 其实就是概率 分析一下复杂度 dp转移是与拓扑排序有关的，每次计算几乎是O(1)的 那么时间复杂度瓶颈就是拓扑排序，故时间复杂度为$O(n+m)$

#include<bits/stdc++.h> using namespace std; const int N=100000+5; int n,m; struct Node{ int v,next; double w; }e[N*2]; int first[N],tot[N],cnt=0; bool vis[N]; double dp[N]; int read(){ int res=0,f=1;char ch=getchar(); while(!isdigit(ch)) f^=ch=='-',ch=getchar(); while(isdigit(ch)) res=(res+(res<<2)<<1)+(ch^48),ch=getchar(); return f?res:-res; } inline void add(int u,int v,double w){ tot[u]++; e[++cnt].v=v; e[cnt].w=w; e[cnt].next=first[u]; first[u]=cnt; } double dfs(int u){ if(vis[u]) return dp[u]; vis[u]=true; dp[u]=0; if(u==n) return dp[u]=0; for(int i=first[u];i;i=e[i].next){ int v=e[i].v; dp[u]+=e[i].w+dfs(v); } dp[u]/=tot[u]; return dp[u]; } int main(){ n=read(),m=read(); memset(tot,0,sizeof(tot)); memset(vis,0,sizeof(vis)); for(int i=1;i<=m;i++){ int a=read(),b=read(); double c; scanf("%lf",&c); add(a,b,c); } printf("%.2lf",dfs(1)); }