CF113D Museum

一、题目

点此看题

二、解法

我拿到这道题就直接写出状态，设$dp[i][j]$为第一个人在$i$，第二个人在$j$的概率，然后就直接高斯消元，$O(n^6)$好像很舒服，列方程的时候分四种情况讨论（这两个人到底动没动），注意不能从$i,i$的状态转移过来。

但是怎么初始化，直接把$f[a][b]$赋值为$1$？好像不是很妥当，因为$dp[a][b]$也可以从其他地方转移过来，但这样概率就大于$1$了（矛盾，冲突 ），此时唯一的办法是改变定义，设$dp[a][b]$为到达第一个人在$a$，第二个人在$b$的期望次数，这样$f[a][b]$就可以大于$1$了，而$f[i][i]$由于是分了这个放在$f[a][b]$的$1$，所以期望即概率。

#include <cstdio> #include <iostream> using namespace std; #define db double const int M = 505; int read() { int num=0,flag=1;char c; while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1; while(c>='0'&&c<='9')num=(num<<3)+(num<<1)+(c^48),c=getchar(); return num*flag; } int n,m,k,A,B,g[M][M],d[M];db a[M][M],p[M]; struct edge { int v,next; }e[2*M]; int id(int x,int y) { return (x-1)*n+y; } void gauss(int n) { for(int i=1;i<=n;i++) { int Max=i; for(int j=i+1;j<=n;j++) if(a[Max][i]<a[j][i]) Max=j; swap(a[Max],a[i]); if(a[i][i]==0) return ; for(int j=1;j<=n;j++) { if(i==j || a[j][i]==0) continue; db t=a[j][i]/a[i][i]; for(int k=i;k<=n+1;k++) a[j][k]-=a[i][k]*t; } } } signed main() { n=read();m=read();A=read();B=read();k=n*n; for(int i=1;i<=m;i++) { int u=read(),v=read(); g[u][v]=g[v][u]=1; d[u]++;d[v]++; } for(int i=1;i<=n;i++) scanf("%lf",&p[i]); a[id(A,B)][k+1]=1; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(i!=j) a[id(i,j)][id(i,j)]=1-p[i]*p[j]; else a[id(i,j)][id(i,j)]=1; for(int k=1;k<=n;k++) if(g[j][k] && i!=k) a[id(i,j)][id(i,k)]-=(1-p[k])/d[k]*p[i]; for(int k=1;k<=n;k++) if(g[i][k] && j!=k) a[id(i,j)][id(k,j)]-=(1-p[k])/d[k]*p[j]; for(int x=1;x<=n;x++) for(int y=1;y<=n;y++) if(g[i][x] && g[j][y] && x!=y) a[id(i,j)][id(x,y)]-=(1-p[x])*(1-p[y])/d[x]/d[y]; } gauss(k); //printf("%.10lf\n",a[id(A,B)][k+1]/a[id(A,B)][id(A,B)]); for(int i=1;i<=n;i++) printf("%.10lf ",a[id(i,i)][k+1]/a[id(i,i)][id(i,i)]); }