题意
给出一个有向图，其中每条边的边长都为1。求这个图中长度恰为 $k$ 的路劲的总数。($1 \leq n \leq 100, 1 \leq k\leq 10^9$)
分析
首先，$k=1$ 时答案就等于边数。
当 $k=2$，$G_2[i][j] = \sum_{w=1}^nG_1[i][w] \times G_1[w][j]$，相当于选取一个中间节点 $w$，只要存在合适的 $w$ ，$u,v$ 之间就存在通路。
以此类推，$G_k = G^k$ 表示恰好走 $k$ 步的情况，只需统计其中非零元素的个数。
这个算法的复杂度为 $O(n^3logn)$.
如果是求 $k$ 步之内的路径数，只需将每种情况累加，即 $S = A+A^2+...+A^k$，这个复杂度也能做到 $O(n^3 log n)$.
#include
#include
using namespace std;
typedef long long ll;
struct matrix
{
int r, c;
int mat[105][105];
matrix(){
memset(mat, 0, sizeof(mat));
}
};
int n, m, k;
matrix mul(matrix A, matrix B) //矩阵相乘
{
matrix ret;
ret.r = A.r; ret.c = B.c;
for(int i = 0;i < A.r;i++)
for(int k = 0;k < A.c;k++)
for(int j = 0;j < B.c;j++)
{
ret.mat[i][j] = (ret.mat[i][j] + A.mat[i][k] * B.mat[k][j]) > 0 ? 1 : 0; //只要区分0和非0即可
}
return ret;
}
matrix mpow(matrix A, int n)
{
matrix ret;
ret.r = A.r; ret.c = A.c;
for(int i = 0;i < ret.r;i++) ret.mat[i][i] = 1;
while(n)
{
if(n & 1) ret = mul(ret, A);
A = mul(A, A);
n >>= 1;
}
return ret;
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
matrix A;
A.r = A.c = n;
for(int i = 0;i < m;i++)
{
int u, v;
scanf("%d%d", &u, &v);
A.mat[u-1][v-1] = 1;
}
A = mpow(A, k);
int ans = 0;
for(int i = 0;i < n;i++)
for(int j = 0;j < n;j++) ans += A.mat[i][j];
printf("%d\n", ans);
return 0;
}