題鏈：

http://www.joyoi.cn/problem/tyvj-2610
題解：

期望dp，高斯消元

對(duì)于每一種到達(dá)i點(diǎn)的方案，都存在一個(gè)概率p，
令dp[i]表示到達(dá)i點(diǎn)的期望次數(shù)，那么容易由期望的定義得出：
dp[i]=p1*1+p2*1+p3*1+......（每個(gè)概率對(duì)應(yīng)的權(quán)值都為1）

如果我們知道了每個(gè)點(diǎn)的期望的到達(dá)次數(shù)，那么在該點(diǎn)期望的爆炸次數(shù)=期望的到達(dá)次數(shù)*P/Q
就可以求出一個(gè)SUM=dp[1]+dp[2]+...+dp[N]
然后每個(gè)點(diǎn)的爆炸的概率就是(dp[i]*P/Q)/(SUM*P/Q)=dp[i]/SUM
(因?yàn)槠谕臋?quán)值都為1,所以概率的比例就等于期望的比例)

這種解法，更容易理解。
http://blog.csdn.net/neither_nor/article/details/52292240
如果在每個(gè)點(diǎn)爆炸的概率不同的話，那應(yīng)該只能像這個(gè)拆點(diǎn)的方法做了。

沒有SPJ，輸出9位小數(shù)才能過2333

代碼：

?

#include<bits/stdc++.h> #define MAXN 305 using namespace std; const double eps=1e-8; struct Edge{int ent;int to[MAXN*MAXN*2],nxt[MAXN*MAXN*2],head[MAXN];Edge():ent(2){}void Adde(int u,int v){to[ent]=v; nxt[ent]=head[u]; head[u]=ent++;to[ent]=u; nxt[ent]=head[v]; head[v]=ent++;} }E; double a[MAXN][MAXN],dp[MAXN],K,SUM; double *A[MAXN]; int cnt[MAXN]; int N,M,P,Q; int dcmp(double x){if(fabs(x)<eps) return 0;return x>0?1:-1; } void buildequation(){for(int i=1;i<=N;i++){a[i][i]=-1;if(i==1) a[i][N+1]=-1;for(int e=E.head[i];e;e=E.nxt[e]){int j=E.to[e];a[i][j]=K*1.0/cnt[j];}}for(int i=1;i<=N;i++) A[i]=a[i]; } void Gausselimination(int pos,int i){if(pos==N+1||i==N+1) return;for(int j=pos;j<=N;j++) if(dcmp(A[pos][i])!=0){swap(A[j],A[pos]); break;}if(dcmp(A[pos][i])!=0)for(int j=pos+1;j<=N;j++){double k=A[j][i]/A[pos][i];for(int l=i;l<=N+1;l++)A[j][l]-=k*A[pos][l];}Gausselimination(pos+(dcmp(A[pos][i])!=0),i+1);if(dcmp(A[pos][i])!=0){for(int l=i+1;l<=N;l++)dp[i]+=A[pos][l]*dp[l];dp[i]=A[pos][N+1]-dp[i];dp[i]=dp[i]/A[pos][i];} } int main(){ios::sync_with_stdio(0);cin>>N>>M>>P>>Q;K=(1-1.0*P/Q);for(int i=1,u,v;i<=M;i++)cin>>u>>v,E.Adde(u,v),cnt[u]++,cnt[v]++;buildequation();Gausselimination(1,1);for(int i=1;i<=N;i++) SUM+=dp[i];cout<<fixed<<setprecision(9);for(int i=1;i<=N;i++) cout<<fabs(dp[i]/SUM)<<endl;return 0; }

?

　　

?

轉(zhuǎn)載于:https://www.cnblogs.com/zj75211/p/8543041.html

總結(jié)

以上是生活随笔為你收集整理的●Joyoi Dotp 驱逐猪猡的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。