鏈接：

#include <stdio.h> int main() {puts("轉載請注明出處[輾轉山河弋流歌 by 空灰冰魂]謝謝");puts("網址：blog.csdn.net/vmurder/article/details/46467217"); }

題解：

呃。拓撲圖上從后往前掃就好了Qwq

代碼：

#include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 101000 using namespace std; struct Eli {int v,l,n;bool f; }e[N<<1]; int head[N],cnt,d[N],D[N]; inline void add(int u,int v,int l) {e[++cnt].v=v;e[cnt].l=l;e[cnt].n=head[u];head[u]=cnt; } double f[N]; queue<int>q; bool vis[N]; int n,m; void bfs() {int i,u,v;q.push(n);while(!q.empty()){vis[u=q.front()]=true,q.pop();for(i=head[u];i;i=e[i].n)if(!vis[v=e[i].v])q.push(v);} } int main() {int i,u,v;int a,b,c;scanf("%d%d",&n,&m);for(i=1;i<=m;i++){scanf("%d%d%d",&a,&b,&c);add(b,a,c),d[a]++;}for(i=1;i<=n;i++)D[i]=d[i]?d[i]:1;bfs();q.push(n);while(!q.empty()){u=q.front(),q.pop(),f[u]/=D[u];for(i=head[u];i;i=e[i].n){if(vis[u])f[v=e[i].v]+=f[u]+e[i].l;if(--d[v]==0)q.push(v);}}printf("%.2lf\n",f[1]);return 0; }

總結

以上是生活随笔為你收集整理的【BZOJ3036】绿豆蛙的归宿 概率DP的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。