[BZOJ3270]博物馆（概率+高斯消元）

2019-11-11 05:50:31

字体：大中小

来源：转载

供稿：网友

题目描述

传送门

题解

假设当前在点(i,j)，下一步从这个点走到它某一个相邻的点的概率即为1−pidi $1-p_i/over d_i$ ，记为goi $go_i$ 设两个人分别走到i,j的概率为f(i,j)，那么 f(i,j)=f(i,j)pipj+∑(i,x),(j,y)∈Ef(x,j)pjgox+f(i,y)pigoy+f(x,y)goxgoy $f(i,j)=f(i,j)p_ip_j+/sum/limits_{(i,x),(j,y)/in E}f(x,j)p_jgo_x+f(i,y)p_igo_y+f(x,y)go_xgo_y$ 特殊地，f(a,b)的初值为1 这样得出了n*n个方程，高斯消元即可需要注意的是，方程中等式右边在同一个f里的两个点不能相等，因为一旦相等就已经结束，不会再有走到这个点的概率

代码

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;#define N 405const double eps=1e-9;int dcmp(double x){ if (x<=eps&&x>=-eps) return 0; return (x>0)?1:-1;}int n,m,A,B,x,y;int tot,point[N],nxt[N*2],v[N*2];double p[N],d[N],go[N],a[N][N],b[N],ans[N];void add(int x,int y){ ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;}int id(int x,int y){ return (x-1)*n+y;}void gauss(){ for (int i=1;i<=n*n;++i) { int num=i; for (int j=i+1;j<=n*n;++j) if (dcmp(a[j][i]-a[num][i])>0) num=j; if (num!=i) { for (int j=1;j<=n*n;++j) swap(a[num][j],a[i][j]); swap(b[num],b[i]); } for (int j=i+1;j<=n*n;++j) if (dcmp(a[j][i])) { double t=a[j][i]/a[i][i]; for (int k=1;k<=n*n;++k) a[j][k]-=t*a[i][k]; b[j]-=b[i]*t; } } for (int i=n*n;i>=1;--i) { for (int j=i+1;j<=n*n;++j) b[i]-=a[i][j]*ans[j]; ans[i]=b[i]/a[i][i]; }}int main(){ scanf("%d%d%d%d",&n,&m,&A,&B); for (int i=1;i<=m;++i) { scanf("%d%d",&x,&y); d[x]+=1.0;d[y]+=1.0; add(x,y);add(y,x); } for (int i=1;i<=n;++i) { scanf("%lf",&p[i]); go[i]=(1-p[i])*1/d[i]; } for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) { a[id(i,j)][id(i,j)]=1; if (i!=j) a[id(i,j)][id(i,j)]-=p[i]*p[j]; for (int k=point[i];k;k=nxt[k]) if (v[k]!=i&&v[k]!=j) a[id(i,j)][id(v[k],j)]=-p[j]*go[v[k]]; for (int k=point[j];k;k=nxt[k]) if (v[k]!=i&&v[k]!=j) a[id(i,j)][id(i,v[k])]=-p[i]*go[v[k]]; for (int k=point[i];k;k=nxt[k]) for (int l=point[j];l;l=nxt[l]) if (v[k]!=v[l]) a[id(i,j)][id(v[k],v[l])]=-go[v[k]]*go[v[l]]; } b[id(A,B)]=1.0; gauss(); for (int i=1;i<=n;++i) PRintf("%.6lf ",ans[id(i,i)]);}

上一篇：P1803 凌乱的yyy

下一篇：26. Remove Duplicates from Sorted Array

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注