您的位置: 首页  >  IT文章  >  HDU 2157 How many ways?? How many ways??

HDU 2157 How many ways?? How many ways??

分类: IT文章 • 2022-08-20 23:49:13

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2695    Accepted Submission(s): 1016


Problem Description
春 天到了, 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的时候输入结束
 
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
 
Sample Output
2 0 1 3
 
Author
小黑
 
Source
2008信息工程学院集训队——选拔赛
Recommend
linle

       定义：设G=<V, E>是一个简单图，它有n个结点V={v1, v2, ... , vn }，则n阶方阵A(G)=(aij)称为G的邻接矩阵。其中

    HDU 2157 How many ways?? How many ways??

      adj表示邻接，nadj表示不邻接。

      定理：设A(G)是图G的邻接矩阵，则(A(G))k 中的i行，j列元素aij(k)等于G中联结vi与vj的长度为k的路的数目。证明见《离散数学》左孝凌。

      计算题目描述的邻接矩阵的k次幂即可得到结果。注意n和m同时为0才结束程序。

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <functional>
#include <string>
#include <cstring>
#include <queue>
#include <set>
#include <cmath>
#include <cstdio>
using namespace std;
#define IOS ios_base::sync_with_stdio(false)
const int INF=0x3f3f3f3f;

const int maxn=25;
const int modnum=1000;
typedef struct matrix{
    int v[maxn][maxn];
    void init(){memset(v,0,sizeof(v));}
}M;
M mul_mod(const M &a,const M &b,int L,int m,int n)
{
    M c; c.init();
    for(int i=0;i<L;i++){
        for(int j=0;j<n;j++){
            for(int k=0;k<m;k++)//注意j，k范围
                c.v[i][j]=(c.v[i][j]+a.v[i][k]*b.v[k][j]%modnum)%modnum;
        }
    }
    return c;
}
M power(M x,int L,int p)
{
    M tmp; tmp.init();
    for(int i=0;i<L;i++)
        tmp.v[i][i]=1;
    while(p){
        if(p&1) tmp=mul_mod(x,tmp,L,L,L);
        x=mul_mod(x,x,L,L,L);
        p>>=1;
    }
    return tmp;
}
int main()
{
    int n,m,s,t,a,b,k;
    M ms,mr;
    while(~scanf("%d%d",&n,&m)&&n+m)
    {
        ms.init();
        for(int i=0;i<m;i++){
            scanf("%d%d",&s,&t);
            ms.v[s][t]=1;
        }
        scanf("%d",&t);
        for(int i=0;i<t;i++)
        {
            scanf("%d%d%d",&a,&b,&k);
            mr=power(ms,n,k);
            printf("%d
",mr.v[a][b]);
        }
    }
}

相关推荐