首页 > 代码库 > 矩阵十题【九】 HDU 2157 How many ways??
矩阵十题【九】 HDU 2157 How many ways??
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=2157
题目大意:给定一个有向图,问从A点恰好走k步(允许重复经过边)到达B点的方案数mod p的值
本来以为是DFS搜索,发现用矩阵也可以做!~ 好神奇。
把 给定的图转为邻接矩阵,即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<iostream> #include<cstring> #include<stdio.h> using namespace std; const int MAX = 32; int n,M=1000; struct Matrix { int v[MAX][MAX]; }; Matrix mtMul(Matrix A, Matrix B) // 求矩阵 A * B { int i, j, k; Matrix C; for(i = 0; i < n; i ++) for(j = 0; j < n; j ++) { C.v[i][j] = 0; for(k = 0; k < n; k ++) C.v[i][j] = (A.v[i][k] * B.v[k][j] + C.v[i][j]) % M; } return C; } Matrix mtPow(Matrix origin,int k) //矩阵快速幂 { int i; Matrix res; memset(res.v,0,sizeof(res.v)); for(i=0;i<n;i++) res.v[i][i]=1; while(k) { if(k&1) res=mtMul(res,origin); origin=mtMul(origin,origin); k>>=1; } return res; } void out(Matrix A) { for(int i=0;i<n;i++) { for(int j=0;j<n;j++) cout<<A.v[i][j]<<" "; cout<<endl; } cout<<endl; } int main () { int m; while(~scanf("%d%d",&n,&m)) { if(m==0&&n==0) break; Matrix A; memset(A.v,0,sizeof(A.v)); int s,e; while(m--) scanf("%d%d",&s,&e),A.v[s][e]=1; //out(A); int T; scanf("%d",&T); while(T--) { int ss,ee,kk; scanf("%d%d%d",&ss,&ee,&kk); Matrix B; B=mtPow(A,kk); cout<<B.v[ss][ee]<<endl; } } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。