一个有 nnn 个结点的无向联通图，在每当 CC 要开一次车时，他会从他当前所在结点随机（等概率的）开向相邻的任意一个结点然后停下来。 现在 CC 想知道，他从 uuu 结点出发，开 stepstepstep 次车，那么经过 vvv 结点（即至少到过一次 vvv 结点）的概率是多少。 样例数据
输入
5 8 2 5 3 2 1 3 4 5 4 2 5 3 4 1 1 2 4 4 5 9 2 4 3 1 4 7 5 3 1
输出
0.89875741 0.53472222 0.83557670 0.33333333
分析：比赛的时候因为某种方式可以过样例，就死磕。。 其实应该用别的方法的。。。。
反着表示不到的概率
int n, m; vector<int> G[maxn]; double dp[55][105]; int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); while(~scanf("%d%d", &n, &m)) { for(int i = 0; i < maxn; ++i) G[i].clear(); for(int i = 0; i < m; ++i) { int u, v; scanf("%d%d", &u, &v); G[u].push_back(v); G[v].push_back(u); } int q; scanf("%d", &q); while(q--) { int u, v, step; scanf("%d%d%d", &u, &v, &step); if(u == v) puts("1.00000000"); else { for(int i = 1; i <= n; ++i) { int len = G[i].size(); int sumv = 0; for(int j = 0; j < len; ++j) { if(G[i][j] == v) { sumv++; } } dp[i][1] = (double)(len - sumv) / len; } for(int i = 2; i <= step; ++i) { for(int j = 1; j <= n; ++j) { if(j == v) continue; int len = G[j].size(); dp[j][i] = 0; for(int k = 0; k < len; ++k) { if(G[j][k] != v) { dp[j][i] += (1.0 / len * dp[G[j][k]][i - 1]); } } } } printf("%.8lf\n", 1 - dp[u][step]);//注意这个地方是u,所以表示的就是从v到u不经过u的概率. } } } return 0; }这种直接用三维表示了,,我打算用二维dp[i][j]表示经过i用了j步的概率…也是可以的,可是我的一个地方少了,
vector<int>g[N]; int vis[N][N][105]; double dp[N][N][105]; double dfs(int u,int to,int step){ if(u==to)return 1.000;//这个地方我写的时候少了.. if(step==0){ return 0.00; } if(vis[u][to][step])return dp[u][to][step]; int sz=g[u].size(); for(int i=0;i<sz;++i){ int v=g[u][i]; dp[u][to][step]+=dfs(v,to,step-1)/sz; } vis[u][to][step]=1; return dp[u][to][step]; } int main(){ while(~sf("%d%d",&n,&m)){ mem(dp,0); rep(i,1,n)g[i].clear(); rep(i,1,m){int u,v;sf("%d%d",&u,&v);g[u].push_back(v);g[v].push_back(u);} int q;sf("%d",&q); mem(vis,0); while(q--){ int u,v,step;sf("%d%d%d",&u,&v,&step); pf("%.10lf\n",dfs(u,v,step)); } } }其实这种是最简洁的.直接把走了第几步到什么地方都表示出来了.
double dp[N][105]; int main(){ while(~sf("%d%d",&n,&m)){ rep(i,1,n)g[i].clear(); rep(i,1,m){ int u,v;sf("%d%d",&u,&v); g[u].push_back(v);g[v].push_back(u); } int q;sf("%d",&q); while(q--){ int u,v,step;sf("%d%d%d",&u,&v,&step); mem(dp,0); if(u==v){ puts("1.0000");continue; } else{ mem(dp,0);dp[u][0]=1.000; //bug //cout<<step<<endl; for(int k=1;k<=step;++k){ for(int i=1;i<=n;++i){ int sz=g[i].size( ); if(i!=v&&dp[i][k-1]>0){ //cout<<i<<endl; for(int j=0;j<sz;++j){ int vv=g[i][j]; //bug dp[vv][k]+=1.0/sz*dp[i][k-1]; } } } } double ans=0; for(int i=1;i<=step;++i){ans+=dp[v][i];} pf("%.10lf\n",ans); } } } }