构建概率矩阵，然后矩阵快速幂，直接输出答案。
1 #include<cstdio> 2 #include<vector> 3 #include<cstring> 4 using namespace std; 5 int n,m,k; 6 vector<int> g[201]; 7 struct matrix 8 { 9 float m[201][201]; 10 matrix(){memset(m,0,sizeof(m));} 11 matrix operator *(const matrix &a)const 12 { 13 matrix tmp; 14 for(int i=0;i<n;i++) 15 for(int j=0;j<n;j++) 16 for(int k=0;k<n;k++) 17 tmp.m[i][j]+=m[i][k]*a.m[k][j]; 18 return tmp; 19 } 20 }; 21 matrix posibility; 22 matrix pow(matrix a,int n) 23 { 24 if(n==1) return a; 25 if(n%2) 26 { 27 matrix tmp=pow(a,n/2); 28 return tmp*tmp*a; 29 } 30 else 31 { 32 matrix tmp=pow(a,n/2); 33 return tmp*tmp; 34 } 35 } 36 int main() 37 { 38 int t; 39 scanf("%d",&t); 40 for(int CASE=1;CASE<=t;CASE++) 41 { 42 scanf("%d%d%d",&n,&m,&k); 43 for(int i=0;i<n;i++) 44 g[i].clear(); 45 while(m--) 46 { 47 int u,v; 48 scanf("%d%d",&u,&v); 49 u--;v--; 50 g[u].push_back(v); 51 g[v].push_back(u); 52 } 53 memset(posibility.m,0,sizeof(posibility.m)); 54 for(int i=0;i<n;i++) 55 { 56 double cnt=g[i].size(); 57 for(int j=0;j<cnt;j++) 58 { 59 int v=g[i][j]; 60 posibility.m[i][v]=1/cnt; 61 } 62 } 63 matrix ans=pow(posibility,k); 64 printf("Case #%d: %.4f ",CASE,ans.m[0][1]); 65 } 66 return 0; 67 }