首页 > 代码库 > 矩阵经典题目八:hdu 2175 How many ways??
矩阵经典题目八:hdu 2175 How many ways??
http://acm.hdu.edu.cn/showproblem.php?pid=2157
给定一个有向图,问从A点恰好走k步(允许重复经过边)到达B点的方案数mod p的值
把给定的图转为邻接矩阵,即A(i,j)=1当且仅当存在一条边i->j。令C=A*A,那么C(i,j)=ΣA(i,k)*A(k,j),实际上就等于从点i到点j恰好经过2条边的路径数(枚举k为中转点)。类似地,C*A的第i行第j列就表示从i到j经过3条边的路径数。同理,如果要求经过k步的路径数,我们只需要二分求出A^k即可。
#include <stdio.h> #include <iostream> #include <map> #include <set> #include <list> #include <stack> #include <vector> #include <math.h> #include <string.h> #include <queue> #include <string> #include <stdlib.h> #include <algorithm> #define LL long long #define _LL __int64 #define eps 1e-12 #define PI acos(-1.0) #define C 240 #define S 20 using namespace std; const int maxn = 25; const int mod = 1000; int n; struct matrix { int mat[maxn][maxn]; void init() { memset(mat,0,sizeof(mat)); for(int i = 0; i < maxn; i++) mat[i][i] = 1; } }a; matrix mul(matrix a, matrix b) { matrix ans; memset(ans.mat,0,sizeof(ans.mat)); for(int i = 0; i < n; i++) { for(int k = 0; k < n; k++) { if(a.mat[i][k] == 0) continue; for(int j = 0; j < n; j++) { ans.mat[i][j] += a.mat[i][k] * b.mat[k][j]%mod; ans.mat[i][j] %= mod; } } } return ans; } matrix pow(matrix a, int n) { matrix ans; ans.init(); while(n) { if(n&1) ans = mul(ans,a); a = mul(a,a); n >>= 1; } return ans; } int main() { int m,T,u,v,k; while(~scanf("%d %d",&n,&m)) { if(n == 0 && m == 0) break; memset(a.mat,0,sizeof(a.mat)); while(m--) { scanf("%d %d",&u,&v); a.mat[u][v] = 1; } scanf("%d",&T); while(T--) { scanf("%d %d %d",&u,&v,&k); matrix ans = pow(a,k); printf("%d\n",ans.mat[u][v]); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。