傳送門
顯然可以狀態轉移：
設 $f[k][x][y]$ 表示第 $k$ 時刻，第一個人在 $x$ ，第二個人在 $y$ 時的概率
那么轉移顯然：
$f[k][x][y]+=\sum_{u}\sum_{v}f[k-1][u][v]*(1-P_u)(1-P_v)/du[u]/du[v]$
其中 $u$ 和 $x$ 有邊相連，$v$ 和 $y$ 有邊向連，$du[i]$ 表示節點 $i$ 的度數，并且 $u!=v$
當然這只是一種情況的轉移，還有三種情況：
$f[k][x][y]+=\sum_{u}f[k-1][u][y]*(1-P_u)P_y/du[u]$
$f[k][x][y]+=\sum_{v}f[k-1][x][v]*(1-P_v)P_x/du[v]$
$f[k][x][y]+=f[k-1][x][y]*P_x*P_y$
然后顯然可以矩陣優化暴力轉移 ，復雜度 $O(n^6log_k)$，$k$ 是轉移步數，精度玄學
正解是考慮設 $f[x][y]$ 表示兩人從起點到終點，經過狀態 $(x,y)$ 即第一個人在 $x$，第二個人在 $y$ 的期望次數
狀態轉移的方程好像也差不多
$f[x][y]+=\sum_{u}\sum_{v}f[u][v]*(1-P_u)(1-P_v)/du[u]/du[v]$
$f[x][y]+=\sum_{u}f[u][y]*(1-P_u)P_y/du[u]$
?
$f[x][y]+=\sum_{v}f[x][v]*(1-P_v)P_x/du[v]$
?
$f[x][y]+=f[x][y]*P_x*P_y$
因為兩人在同一個點時就不會繼續走了，所以從起點出發兩人在 $i$ 點相遇的概率就是兩人從起點到終點，經過狀態 $(i,i)$ 的期望次數（$f[i][i]$）
這個方程轉移有環，可以列出所有轉移方程然后用高斯消元解方程組
復雜度 $O(n^6)$
?
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; typedef double db; inline int read() {int x=0,f=1; char ch=getchar();while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }return x*f; } const int N=507; int fir[N],from[N<<1],to[N<<1],cntt; inline void add(int a,int b) { from[++cntt]=fir[a],fir[a]=cntt,to[cntt]=b; } int n,m,nn,pa,pb,id[N][N],du[N]; db P[N],A[N][N],ans[N]; void Gauss()//高斯消元解方程組 {int pos;for(int i=1;i<=nn;i++){pos=0;for(int j=i;j<=nn;j++) if(fabs(A[j][i])>fabs(A[pos][i])||!pos) pos=j;swap(A[i],A[pos]);for(int j=i+1;j<=nn;j++){db w=A[j][i]/A[i][i];for(int k=i;k<=nn+1;k++) A[j][k]-=w*A[i][k];}}for(int i=nn;i;i--){for(int j=i+1;j<=nn;j++) A[i][nn+1]-=ans[j]*A[i][j];ans[i]=A[i][nn+1]/A[i][i];} } int main() {n=read(),m=read(),pa=read(),pb=read();nn=n*n; int now=0,a,b;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) id[i][j]=++now;for(int i=1;i<=m;i++){a=read(),b=read();add(a,b); add(b,a);du[a]++; du[b]++;}for(int i=1;i<=n;i++) scanf("%lf",&P[i]);for(int i=1;i<=n;i++)//枚舉ufor(int j=1;j<=n;j++)//枚舉v {if(i==j) continue;//注意如果i=j就不能轉移for(int k=fir[i];k;k=from[k])//枚舉xfor(int l=fir[j];l;l=from[l])//枚舉yA[ id[to[k]][to[l]] ][id[i][j]]-=(1.0-P[i])*(1.0-P[j])/du[i]/du[j];for(int k=fir[i];k;k=from[k]) A[ id[to[k]][j] ][id[i][j]]-=(1.0-P[i])*P[j]/du[i];for(int k=fir[j];k;k=from[k]) A[ id[i][to[k]] ][id[i][j]]-=(1.0-P[j])*P[i]/du[j];A[id[i][j]][id[i][j]]-=P[i]*P[j];//構造矩陣 }for(int i=1;i<=nn;i++) A[i][i]++;A[id[pa][pb]][nn+1]=1;//起點初始為1 Gauss();for(int i=1;i<=n;i++) printf("%.6lf ",ans[id[i][i]]);return 0; }
?
)
