How many ways??
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1562 Accepted Submission(s): 546
Problem Description
春
天到了, HDU校园里开满了花, 姹紫嫣红, 非常美丽. 葱头是个爱花的人, 看着校花校草竞相开放, 漫步校园, 心情也变得舒畅.
为了多看看这迷人的校园, 葱头决定, 每次上课都走不同的路线去教室, 但是由于时间问题, 每次只能经过k个地方, 比方说,
这次葱头决定经过2个地方, 那他可以先去问鼎广场看看喷泉, 再去教室, 也可以先到体育场跑几圈, 再到教室. 他非常想知道, 从A
点恰好经过k个点到达B点的方案数, 当然这个数有可能非常大, 所以你只要输出它模上1000的余数就可以了. 你能帮帮他么??
你可决定了葱头一天能看多少校花哦
天到了, HDU校园里开满了花, 姹紫嫣红, 非常美丽. 葱头是个爱花的人, 看着校花校草竞相开放, 漫步校园, 心情也变得舒畅.
为了多看看这迷人的校园, 葱头决定, 每次上课都走不同的路线去教室, 但是由于时间问题, 每次只能经过k个地方, 比方说,
这次葱头决定经过2个地方, 那他可以先去问鼎广场看看喷泉, 再去教室, 也可以先到体育场跑几圈, 再到教室. 他非常想知道, 从A
点恰好经过k个点到达B点的方案数, 当然这个数有可能非常大, 所以你只要输出它模上1000的余数就可以了. 你能帮帮他么??
你可决定了葱头一天能看多少校花哦
Input
输
入数据有多组, 每组的第一行是2个整数 n, m(0 < n <= 20, m <= 100) 表示校园内共有n个点,
为了方便起见, 点从0到n-1编号,接着有m行, 每行有两个整数 s, t (0<=s,t<n) 表示从s点能到t点,
注意图是有向的.接着的一行是两个整数T,表示有T组询问(1<=T<=100),
接下来的T行, 每行有三个整数 A, B, k, 表示问你从A 点到 B点恰好经过k个点的方案数 (k < 20), 可以走重复边。如果不存在这样的走法, 则输出0
当n, m都为0的时候输入结束
入数据有多组, 每组的第一行是2个整数 n, m(0 < n <= 20, m <= 100) 表示校园内共有n个点,
为了方便起见, 点从0到n-1编号,接着有m行, 每行有两个整数 s, t (0<=s,t<n) 表示从s点能到t点,
注意图是有向的.接着的一行是两个整数T,表示有T组询问(1<=T<=100),
接下来的T行, 每行有三个整数 A, B, k, 表示问你从A 点到 B点恰好经过k个点的方案数 (k < 20), 可以走重复边。如果不存在这样的走法, 则输出0
当n, m都为0的时候输入结束
Output
计算每次询问的方案数, 由于走法很多, 输出其对1000取模的结果
Sample Input
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
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
Sample Output
2
0
1
3
0
1
3
Author
小黑
Source
对于这道题,不能不说构思确实很精妙,之前学的线性代数,居然没有注意这一点,╮(╯▽╰)╭。每一次都会从一个点遍历到所有的点,然后将其可能性累加,这不就是矩阵的特性吗,╮(╯▽╰)╭。
好了,做法其实还是很单纯的,只是如果没有想到的话,估计很难做出来。构造一个邻接矩阵,对应的点如果能联通就涂1,这样就完美的转化为一个矩阵。对于每一次进行一次矩阵求解即可。O(∩_∩)O哈哈~
代码: 105ms c++
//#define LOCAL
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int mat[][];
int ans[][];
int sav[][];
int n,m,t;
void init(int ans[][])
{
for(int i=;i<n;i++)
{
for(int j=;j<n;j++)
{
if(i==j) ans[i][j]=;
else ans[i][j]=;
}
}
} void Matrix(int a[][],int b[][])
{
int cc[][]={};
for(int i=;i<n;i++)
{
for(int j=;j<n;j++)
{
for(int k=;k<n;k++)
{
cc[i][j]=(cc[i][j]+a[i][k]*b[k][j])%;
}
}
}
for(int i=;i<n;i++)
{
for(int j=;j<n;j++)
{
a[i][j]=cc[i][j];
}
}
} void pow(int w)
{
while(w>)
{
if(w&) Matrix(ans,mat);
w>>=;
if(w==)break;
Matrix(mat,mat);
}
} void input()
{
int a,b,k;
memset(sav,,sizeof(sav));
while(m--){
scanf("%d%d",&a,&b);
sav[a][b]=;
}
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&a,&b,&k);
for(int i=;i<n;i++)
{
for(int j=;j<n;j++)
mat[i][j]=sav[i][j];
}
init(ans);
pow(k);
printf("%d\n",ans[a][b]);
}
} int main()
{
#ifdef LOCAL
freopen("test.in","r",stdin);
#endif
while(~scanf("%d%d",&n,&m)&&n+m!=)
input();
return ;
}