http://www.lydsy.com/JudgeOnline/problem.php?id=3270

---

題意：一張無向圖，一開始兩人分別在$x$和$y$，每一分鐘在點(diǎn)$i$不走的概率為$p[i]$,走的話等概率走到相鄰的點(diǎn)，求兩人在每個(gè)點(diǎn)相遇的概率
對(duì)于100%的數(shù)據(jù)有 n <= 20，n-1 <= m <= n(n-1)/2

---

?

因?yàn)閮蓚€(gè)人，所以狀態(tài)肯定要二元組呀
$f(i,j)$表示一人在$i$另一人在$j$的概率，轉(zhuǎn)移方程：
$f(i,j)=f(i,j)p_ip_j-\sum\limits_{(x,i)\ ,\ (y,j) \in E}{f(x,i)p_jt_x+f(i,y)p_it_y+f(x,y)t_xt_y}$
$t_i=\frac{1-p_i}{d_i}$
然后有環(huán)沒法$DP$.....
高斯消元解方程...$n^2$個(gè)方程$n^2$個(gè)變量

注意：
$1.$ $f(i,i)$不能走到其他啦(也不能不走啦)
$2.$ 一開始$f(x,y)$的概率除了走出來的左面還要加上$1$，因?yàn)橐婚_始一定在$(x,y)$

?

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; typedef long long ll; const int N=405,M=405; inline int read(){char c=getchar();int x=0;while(c<'0'||c>'9'){c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x; } int n,m,x,y,u,v,nn; int d[N]; double p[N],a[N][N]; inline int id(int i,int j){return (i-1)*n+j;} struct edge{int v,ne; }e[M<<1]; int h[N],cnt=0; inline void ins(int u,int v){cnt++;e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;cnt++;e[cnt].v=u;e[cnt].ne=h[v];h[v]=cnt; } double t[N]; void buildEquation(){for(int i=1;i<=n;i++) t[i]=(1-p[i])/d[i];for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){int num=id(i,j);double *g=a[num];if(i==j) g[num]=1;else g[num]=1-p[i]*p[j];int x,y;for(int k=h[i];k;k=e[k].ne){x=e[k].v;if(x!=j) g[id(x,j)]=-p[j]*t[x];}for(int k=h[j];k;k=e[k].ne){y=e[k].v;if(y!=i) g[id(i,y)]=-p[i]*t[y];}for(int k=h[i];k;k=e[k].ne)for(int l=h[j];l;l=e[l].ne){x=e[k].v,y=e[l].v;if(x!=y) g[id(x,y)]=-t[x]*t[y];}}a[id(x,y)][nn+1]=1; } void GaussElimination(int n){for(int i=1;i<=n;i++){int r=i;for(int j=i+1;j<=n;j++)if(abs(a[j][i])>abs(a[r][i])) r=j;if(r!=i) for(int k=1;k<=n+1;k++) swap(a[i][k],a[r][k]);for(int j=i+1;j<=n;j++){double t=a[j][i]/a[i][i];for(int k=i;k<=n+1;k++) a[j][k]-=a[i][k]*t;}}for(int i=n;i>=1;i--){for(int j=n;j>i;j--) a[i][n+1]-=a[j][n+1]*a[i][j];a[i][n+1]/=a[i][i];} } int main(){freopen("in","r",stdin);n=read();m=read();nn=n*n;x=read();y=read();for(int i=1;i<=m;i++) u=read(),v=read(),ins(u,v),d[u]++,d[v]++;for(int i=1;i<=n;i++) scanf("%lf",&p[i]);buildEquation();GaussElimination(nn);for(int i=1;i<=n;i++) printf("%.6lf ",a[id(i,i)][nn+1]); }

?

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

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

總結(jié)

以上是生活随笔為你收集整理的BZOJ 3270: 博物馆 [概率DP 高斯消元]的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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