http://acm.hdu.edu.cn/showproblem.php?pid=4035

獲得：

1、首先推斷是不是樹。事實上，所有的感覺身影，既看邊數==算-1是不成立 ?

2、有時候，我告訴孩子來區分樹仍然是必要的，就是，只是是在dfs的時候，傳參數的時候多加個表示父節點的參數而已

3、一定注意，概率DP對精度真的要求非常高 開始的時候寫1e-8,WA了好幾發，改了1e-10 ?AC

4、注意分母為0的可能的時候加上推斷

講的非常具體的題解：http://blog.csdn.net/morgan_xww/article/details/6776947

直接按公式寫的代碼就是：

#include <cstdio> #include <cstring> #include <algorithm> #include <string> #include <iostream> #include <iomanip> #include <cmath> #include <map> #include <set> #include <queue> using namespace std;#define ls(rt) rt*2 #define rs(rt) rt*2+1 #define ll long long #define ull unsigned long long #define rep(i,s,e) for(int i=s;i<e;i++) #define repe(i,s,e) for(int i=s;i<=e;i++) #define CL(a,b) memset(a,b,sizeof(a)) #define IN(s) freopen(s,"r",stdin) #define OUT(s) freopen(s,"w",stdout) const ll ll_INF = ((ull)(-1))>>1; const double EPS = 1e-10; const int INF = 100000000; const int MAXN = 10000+100;vector<int>g[MAXN]; double k[MAXN],e[MAXN]; double a[MAXN],b[MAXN],c[MAXN]; int n;bool sea(int i, int fa) {if(g[i].size() == 1 && fa!=-1)//葉子節點{a[i]=k[i];c[i]=b[i]=1.0-k[i]-e[i];return true;}//非葉子節點,此時該非葉子節點的子孫都已經遍歷過了double aa=0.0,bb=0.0,cc=0.0;for(int j=0;j<g[i].size();j++){if( g[i][j] == fa)continue;if(!sea(g[i][j],i))return 0;aa+=a[g[i][j]];bb+=b[g[i][j]];cc+=c[g[i][j]];}int m=g[i].size();a[i]=(k[i]+(1-k[i]-e[i])/m*aa)/(1-(1.0-k[i]-e[i])/m*bb);b[i]=(1.0-k[i]-e[i])/m/(1.0-(1.0-k[i]-e[i])/m*bb);c[i]=( (1.0-k[i]-e[i])+(1.0-k[i]-e[i])/m*cc )/(1.0 -(1.0-k[i]-e[i])/m*bb);return true; }int main() {int ncase,u,v,ic=0;scanf("%d",&ncase);while(ncase--){scanf("%d",&n);for(int i=1;i<=n;i++)g[i].clear();for(int i=1;i<n;i++){scanf("%d%d",&u,&v);g[u].push_back(v);g[v].push_back(u);}for(int i=1;i<=n;i++){scanf("%lf%lf",&k[i],&e[i]);k[i]/=100.0;e[i]/=100.0;}printf("Case %d: ",++ic);if(sea(1,-1) && fabs(1.0-a[1])>EPS)printf("%.6lf\n",c[1]/(1.0-a[1]));elseprintf("impossible\n");}return 0; }
當然更好的寫法還是題解上的

#include <cstdio> #include <iostream> #include <vector> #include <cmath> using namespace std; const int MAXN = 10000 + 5; double e[MAXN], k[MAXN]; double A[MAXN], B[MAXN], C[MAXN]; vector<int> v[MAXN]; bool search(int i, int fa) { if ( v[i].size() == 1 && fa != -1 ) { A[i] = k[i]; B[i] = 1 - k[i] - e[i]; C[i] = 1 - k[i] - e[i]; return true; } A[i] = k[i]; B[i] = (1 - k[i] - e[i]) / v[i].size(); C[i] = 1 - k[i] - e[i]; double tmp = 0; for (int j = 0; j < (int)v[i].size(); j++) { if ( v[i][j] == fa ) continue; if ( !search(v[i][j], i) ) return false; A[i] += A[v[i][j]] * B[i]; C[i] += C[v[i][j]] * B[i]; tmp += B[v[i][j]] * B[i]; } if ( fabs(tmp - 1) < 1e-10 ) return false; A[i] /= 1 - tmp; B[i] /= 1 - tmp; C[i] /= 1 - tmp; return true; } int main() { int nc, n, s, t; cin >> nc; for (int ca = 1; ca <= nc; ca++) { cin >> n; for (int i = 1; i <= n; i++) v[i].clear(); for (int i = 1; i < n; i++) { cin >> s >> t; v[s].push_back(t); v[t].push_back(s); } for (int i = 1; i <= n; i++) { cin >> k[i] >> e[i]; k[i] /= 100.0; e[i] /= 100.0; } cout << "Case " << ca << ": "; if ( search(1, -1) && fabs(1 - A[1]) > 1e-10 ) cout << C[1]/(1 - A[1]) << endl; else cout << "impossible" << endl; } return 0; }

版權聲明：本文博客原創文章，博客，未經同意，不得轉載。

轉載于:https://www.cnblogs.com/gcczhongduan/p/4659445.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的hdu 4035 可能性DP 成都网络游戏的全部內容，希望文章能夠幫你解決所遇到的問題。

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