题意：
给定n个点m条边的无向图
问：
从任意点出发任意走d步，从不经过某个点的概率
dp[i][j]表示从不经过i点的前提下，走了d步到达j点的概率。
#include
#include
#include
#include
#include
#include
#include
using namespace std; #define N 55 #define eps (1e-8) struct Edge{ int from, to, nex; }edge[N*N*N]; int head[N], edgenum; void init(){memset(head, -1, sizeof head); edgenum = 0;} void add(int u, int v){ Edge E = {u,v,head[u]}; edge[edgenum] = E; head[u] = edgenum++; } double dp[2][N][N], siz[N]; int n, m, d; void solve(){ scanf("%d %d %d", &n, &m, &d); init(); int u, v; for(int i = 1; i <= n; i++)siz[i] = 0.0; while(m--){ scanf("%d %d",&u,&v); add(u,v); add(v,u); siz[u] += 1.0; siz[v] += 1.0; } int cur = 0; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(i == j) dp[cur][i][j] = 0; else dp[cur][i][j] = 1.0/(double)n; while(d--) { cur ^= 1; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) dp[cur][i][j] = 0; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(i!=j) { double Size = siz[j]; if(Size < eps)continue; for(int k = head[j]; ~k; k = edge[k].nex) if(edge[k].to != i) { dp[cur][i][edge[k].to] += dp[cur^1][i][j] / Size; } } } for(int i = 1; i <= n; i++) { double ans = 0; for(int j = 1; j <= n; j++) ans += dp[cur][i][j]; printf("%.10f\n", ans); } } int main(){ int T;scanf("%d",&T); while(T--){ solve(); } return 0; } /* 3 3 2 1 2 2 3 3 1 */