广东建设公司网站,wordpress 文章链接失效,泉州网上房地产,保险网站定制题意#xff1a;一张 nnn 个点的无向连通图#xff0c;两个人开始时分别在 a,ba,ba,b。每次在 uuu 时会以 ppp 的概率原地不动#xff0c;1−p1-p1−p 的概率等概率随机选择到一个相邻的点#xff0c;当两人在同一点时停止。分别求在每个点相遇的概率。 n≤22n\leq 22n≤22…题意一张 nnn 个点的无向连通图两个人开始时分别在 a,ba,ba,b。每次在 uuu 时会以 ppp 的概率原地不动1−p1-p1−p 的概率等概率随机选择到一个相邻的点当两人在同一点时停止。分别求在每个点相遇的概率。
n≤22n\leq 22n≤22
网上一堆 “从起点走到 (i,j)(i,j)(i,j) 的概率”看得我一脸懵逼……
很容易分析出转移矩阵 MMM然后相当于求这个东西
limt→∞MtV\lim_{t\to \infin}M^{t}Vt→∞limMtV
但这个并没有通用的求法因为矩阵的特征向量有无数多个。
算法一
比较直观的解法。
设 f(i,j)f(i,j)f(i,j) 表示 (i,j)(i,j)(i,j) 这个状态到达次数的期望即这个状态在所有世界线中出现次数的平均值。
由于最终点只有可能出现 000 次或 111 次所以它的期望次数就是概率。
而这个期望随便消一下就可以算出来。
算法二
比较本质的解法。
考虑枚举一个最终状态 (s,s)(s,s)(s,s)在此条件下求 f(i,j)f(i,j)f(i,j) 表示最终到这个状态的概率令 f(i,i)[is]f(i,i)[is]f(i,i)[is],就可以消元了。但这样是 O(n7)O(n^7)O(n7) 的无法通过。
考虑一次性把每个点作为终点的 nnn 个答案算出来即构建出 (n2−n)×(n2)(n^2-n)\times (n^2)(n2−n)×(n2) 的矩阵。这样有 n2n^2n2 个未知数但只有 n2−nn^2-nn2−n 个方程无法解出但可以求出 f(a,b)f(a,b)f(a,b) 关于 f(1,1),f(2,2),…,f(n,n)f(1,1),f(2,2),\dots,f(n,n)f(1,1),f(2,2),…,f(n,n) 的线性表达就可以求出答案了。
复杂度 O(n6)O(n^6)O(n6)
所以算法一算法二以及上面那个假算法写出来都一样的……
#include iostream
#include cstdio
#include cstring
#include cctype
#include cmath
#include vector
using namespace std;
vectorint e[25];
double p[25],a[505][505];
int n,m,sa,sb;
inline int id(int x,int y)
{if (xy) return n*n-nx;return (x-1)*(n-1)y-(yx);
}
void gauss(int n,int m)
{for (int i1;in;i){int posi;for (int ji1;jn;j) if (fabs(a[j][i])fabs(a[pos][i])) posj;if (posi) swap(a[i],a[pos]);for (int j1;jn;j)if (j!i){double ta[j][i]/a[i][i];for (int ki;km;k)a[j][k]-t*a[i][k];}}
}
int main()
{scanf(%d%d%d%d,n,m,sa,sb);if (sasb){for (int i1;in;i) if (isa) printf(%.10f ,1.0);else printf(%.10f ,0.0);return 0;}for (int i1;im;i){int u,v;scanf(%d%d,u,v);e[u].push_back(v),e[v].push_back(u);}for (int i1;in;i) scanf(%lf,p[i]);for (int u1;un;u)for (int v1;vn;v)if (u!v){int sid(u,v);double pu1.0/e[u].size(),pv1.0/e[v].size();for (int i0;i(int)e[u].size();i)for (int j0;j(int)e[v].size();j){double t(i(int)e[u].size()? (1-p[u])*pu:p[u])*(j(e[v].size())? (1-p[v])*pv:p[v]);a[s][id(i(int)e[u].size()? e[u][i]:u,j(int)e[v].size()? e[v][j]:v)]t;}a[s][s]-1;}gauss(n*n-n,n*n);int sid(sa,sb);for (int in*n-n1;in*n;i) printf(%.10f ,-a[s][i]/a[s][s]);return 0;
}
