一个数据包在一个无向网络中传递。在时刻0，该数据包将依照特定的概率随机抵达网络中的某个节点。
网络可以看做一张完全带权无向图，包含N个节点，若t时刻数据包在节点i，则在t+1时刻，数据包被传递到节点j的概率是d(i,j)/(∑kd(i,k))
其中d(i,j)表示节点i到节点j的最短路径的长度。在传递到下一个节点后，该数据包会自动删除在当前节点的备份。现在，给定数据包0时刻在每个节点的概率和网络的每条边权。求T时刻数据包在每个节点的概率。输入格式第一行两个整数N和T。第二行N个实数，表示0时刻数据包在每个节点的概率（保证概率加起来为1）。接下来N行每行N个整数,第i行第j个数表示节点i和节点j之间的边权。保证第i行第i个数为0且第i行第j个数等于第j行第i个数。输出格式输出共N行，第i行表示T时刻数据包在节点i的概率，保留六位小数。数据范围与约定对于50%的数据，T≤20。对于100%的数据,N≤200,T≤10^9。保证对于每个点d的和值在int范围。样例输入3 20 1 00 1 41 0 24 2 0样例输出0.4000000.3500000.250000首先列出dp式f[t][v]=∑uf[t-1][u]*(d(u,v)/(∑kd(u,k)))
显然含有矩阵快速幂的特点，写出矩阵，假设n=3
0 d(1,2)/(∑kd(1,k)) d(1,3)/(∑kd(1,k))
d(2,1)/(∑kd(2,k)) 0 d(2,3)/(∑kd(2,k))
d(3,1)/(∑kd(3,k)) d(3,2)/(∑kd(3,k)) 0
d的话直接弗洛伊德
转移矩阵Mat[i][j]=d(i,j)/(∑kd(i,k))
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 struct Matrix 7 { 8 double a[302][302]; 9 }Mat,pre,st,ans;10 int n,T;11 double s[301],map[301][301];12 Matrix operator *(const Matrix &x,const Matrix &y)13 {14 Matrix res;15 int i,j,k;16 memset(res.a,0,sizeof(res.a));17 for (i=1;i<=n;i++)18 {19 for (j=1;j<=n;j++)20 {21 for (k=1;k<=n;k++)22 {23 res.a[i][j]+=x.a[i][k]*y.a[k][j];24 }25 }26 }27 return res;28 }29 void qpow(int x)30 { int i;31 for (i=1;i<=n;i++)32 ans.a[i][i]=1;33 while (x)34 {35 if (x&1) ans=ans*Mat;36 Mat=Mat*Mat;37 x/=2;38 }39 }40 int main()41 { int i,j,k;42 cin>>n>>T;43 memset(pre.a,0,sizeof(pre.a));44 memset(Mat.a,0,sizeof(Mat.a));45 for (i=1;i<=n;i++)46 scanf("%lf",&pre.a[1][i]);47 for (i=1;i<=n;i++)48 {49 for (j=1;j<=n;j++)50 {51 scanf("%lf",&map[i][j]);52 }53 }54 for (k=1;k<=n;k++)55 for (i=1;i<=n;i++)56 if (i!=k)57 for (j=1;j<=n;j++)58 if (i!=j&&k!=j)59 map[i][j]=min(map[i][j],map[i][k]+map[k][j]);60 for (i=1;i<=n;i++)61 for (j=1;j<=n;j++)62 if (i!=j) s[i]+=map[i][j];63 for (i=1;i<=n;i++)64 { for (j=1;j<=n;j++)65 if (i!=j)66 Mat.a[j][i]=map[j][i]/s[j];67 }68 qpow(T);69 ans=pre*ans;70 for (i=1;i<=n;i++)71 printf("%.6lf\n",ans.a[1][i]);72 }