【Hdu2157】多少条路呢

来源和评测点

小黑
2008信息工程学院集训队——选拔赛
Hdu2157
Caioj1485

题目

【题目大意】
给定一个有向图,有n个点,m条边。求A点到B点恰好经过k条边的方案数(可走重复边)
【输入格式】
输入数据有多组,每组第一行有两个整数,n(1<=n<=20),m(m<=100),
表示有n个点,m条边,点的编号为0~n-1。
接下来m行,每行有两个整数,x,y,表示x点能到y点。
接下的一行有一个整数,t(1<=t<=100),表示有t组询问。
接着的t行,每行有三个整数,A,B,k(k<20),表示问你从A点到B点恰好经过k条边的方案数,
由于可能方案数非常大,所以只要计算方案数mod 1000.
当n,m为0时,输入结束。
【输出格式】
输出每次询问的方案数(记得要对1000取模)
【输入样例】
4 4
0 1
0 2
1 3
2 3
2
0 3 2
0 3 3
3 6
0 1
1 0
0 2
2 0
1 2
2 1
2
1 2 1
0 1 3
0 0
【输出样例】
2
0
1
3

分析

这道题还是非常有趣的
考虑邻接矩阵的自乘
因为有0的话必定无法对结果矩阵作出贡献,
所以结果矩阵f[i,j]的值必定是f[i,k]后f[k,j]的总方案数
(也就是k=2的情况)
那么同理,k的其他情况就是邻接矩阵的k次幂

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
//*******************全局常量*******************
const int MAXN=35;
//*******************全局定义*******************
struct matrix
{
int row,col;
int p[MAXN][MAXN];
matrix()
{
memset(p,0,sizeof(p));
}
};
//*******************全局变量*******************
int mod=1000;
//*******************实现*******************
matrix cheng(matrix a,matrix b)
{
matrix c;
int n=a.row,m=a.col,p=b.col;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
c.p[i][j]=(c.p[i][j]+a.p[i][k]*b.p[k][j])%mod;
c.row=n;c.col=p;
return c;
}
//*******************主函数*******************
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==0 and m==0) break;
matrix f[20];f[1].row=f[1].col=n;
for(int i=1;i<=m;i++)
{
int x,y;scanf("%d%d",&x,&y);
f[1].p[x+1][y+1]=1;
}
for(int i=2;i<=19;i++) f[i]=cheng(f[1],f[i-1]);
for(int i=1;i<=n;i++) f[0].p[i][i]=1;//debug
int t;scanf("%d",&t);
while(t--)
{
int x,y,k;scanf("%d%d%d",&x,&y,&k);
printf("%d\n",f[k].p[x+1][y+1]);
}
}
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2018-01/多少条路呢.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%