看空间网站,wap网站推荐,口碑营销最新案例,中国空间站有哪些国家加入传送门 显然可以状态转移#xff1a; 设 $f[k][x][y]$ 表示第 $k$ 时刻#xff0c;第一个人在 $x$ #xff0c;第二个人在 $y$ 时的概率 那么转移显然#xff1a; $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$ 有边相连#xff…传送门 显然可以状态转移 设 $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)$ #includeiostream
#includecstdio
#includealgorithm
#includecstring
#includecmath
using namespace std;
typedef long long ll;
typedef double db;
inline int read()
{int x0,f1; char chgetchar();while(ch0||ch9) { if(ch-) f-1; chgetchar(); }while(ch0ch9) { x(x1)(x3)(ch^48); chgetchar(); }return x*f;
}
const int N507;
int fir[N],from[N1],to[N1],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 i1;inn;i){pos0;for(int ji;jnn;j) if(fabs(A[j][i])fabs(A[pos][i])||!pos) posj;swap(A[i],A[pos]);for(int ji1;jnn;j){db wA[j][i]/A[i][i];for(int ki;knn1;k) A[j][k]-w*A[i][k];}}for(int inn;i;i--){for(int ji1;jnn;j) A[i][nn1]-ans[j]*A[i][j];ans[i]A[i][nn1]/A[i][i];}
}
int main()
{nread(),mread(),paread(),pbread();nnn*n; int now0,a,b;for(int i1;in;i)for(int j1;jn;j) id[i][j]now;for(int i1;im;i){aread(),bread();add(a,b); add(b,a);du[a]; du[b];}for(int i1;in;i) scanf(%lf,P[i]);for(int i1;in;i)//枚举ufor(int j1;jn;j)//枚举v{if(ij) continue;//注意如果ij就不能转移for(int kfir[i];k;kfrom[k])//枚举xfor(int lfir[j];l;lfrom[l])//枚举yA[ id[to[k]][to[l]] ][id[i][j]]-(1.0-P[i])*(1.0-P[j])/du[i]/du[j];for(int kfir[i];k;kfrom[k]) A[ id[to[k]][j] ][id[i][j]]-(1.0-P[i])*P[j]/du[i];for(int kfir[j];k;kfrom[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 i1;inn;i) A[i][i];A[id[pa][pb]][nn1]1;//起点初始为1Gauss();for(int i1;in;i) printf(%.6lf ,ans[id[i][i]]);return 0;
} 转载于:https://www.cnblogs.com/LLTYYC/p/10837689.html
