网站短链接生成器,wordpress 分享 网站,用vs2013网站开发,python做网站的 框架题干#xff1a;
给出一个 n * n 的邻接矩阵A.
A是一个01矩阵 .
A[i][j]1表示i号点和j号点之间有长度为1的边直接相连.
求出从 1 号点 到 n 号点长度为k的路径的数目.
输入描述:
第1行两个数n,k (20 ≤n ≤ 30,1 ≤ k ≤ 10)
第2行至第n1行#xff0c;为一个邻接矩阵
…题干
给出一个 n * n 的邻接矩阵A.
A是一个01矩阵 .
A[i][j]1表示i号点和j号点之间有长度为1的边直接相连.
求出从 1 号点 到 n 号点长度为k的路径的数目.
输入描述:
第1行两个数n,k (20 ≤n ≤ 30,1 ≤ k ≤ 10)
第2行至第n1行为一个邻接矩阵
输出描述:
题目中所求的数目
示例1
输入
复制
4 2
0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0
输出
复制
2
说明 样例如图:
第一条路径1-2-4
第二条路径1-3-4 解题报告 这题用离散数学的那些关系矩阵的知识就可以求解了。直接求矩阵的k次方。 其实这题数据还可以再加强数据量大的话矩阵快速幂。
AC代码
#includeiostream
#includecstdio
using namespace std;
#define ll long long
struct matrix {ll arr[35][35];
} ;//不要设置全局变量了 不好初始化
matrix unitMetrix;
int n,k;
matrix Mul(matrix a,matrix b) {matrix ans;for(int i 1 ; in; i) {for(int j 1 ; jn; j) {ans.arr[i][j]0;for(int k 1 ; kn; k) {ans.arr[i][j] a.arr[i][k]*b.arr[k][j];}}}return ans;
}int main()
{matrix tmp,a;cinnk;for(int i 1; in; i) {for(int j 1; jn; j) {scanf(%lld,a.arr[i][j]);}}tmp a;for(int i 1; ik-1; i) {tmp Mul(a,tmp);}printf(%lld\n,tmp.arr[1][n]);return 0 ;
}
