【传递闭包】HDU 2157 How many ways??

UPD：现在才发现本题是个传递闭包

题目内容

春天到了,HDU校园里开满了花,姹紫嫣红,非常美丽. 葱头是个爱花的人,看着校花校草竞相开放,漫步校园,心情也变得舒畅. 为了多看看这迷人的校园,葱头决定,每次上课都走不同的路线去教室,但是由于时间问题,每次只能经过$k$个地方,比方说,这次葱头决定经过2个地方,那他可以先去问鼎广场看看喷泉,再去教室,也可以先到体育场跑几圈,再到教室. 他非常想知道,从A 点恰好经过$k$个点到达B点的方案数,当然这个数有可能非常大,所以你只要输出它模上1000的余数就可以了. 你能帮帮他么?? 你可决定了葱头一天能看多少校花哦。

输入格式

输入数据有多组,每组的第一行是2个整数$n,m$($0 < n \le 20,m \le 100$) 表示校园内共有$n$个点,为了方便起见,点从$0$到$n-1$编号,接着有$m$行,每行有两个整数$ s,t $($0\le s,t<n$) 表示从$s$点能到$t$点,注意图是有向的.接着的一行是两个整数$T$,表示有$T$组询问($1\le T\le 100$)。

接下来的$T$行,每行有三个整数$ A,B,k$,表示问你从A点到B点恰好经过$k$个点的方案数($k < 20$),可以走重复边。如果不存在这样的走法,则输出$0$。

当$n,m$都为$0$的时候输入结束

输出格式

计算每次询问的方案数,由于走法很多,输出其对1000取模的结果

样例输入

(??)

1 2

2 8

样例输出

4

()()

思路

令$Mat[i][j]=1$，表示从$i$到$j$连通，即$i,j$经过一个点到达的方案数为1。那么$∑(M[i][k] + M[k][j])$,$k∈(0, N-1)$, 就表示$i,j$经过两个点到达的方案数。即将矩阵$Mat^n$就可以求出$i,j$经过要求个数个点到达的方案数。

代码

#include<iostream>

#include<cstring>

#include<cstdio>

#include<string>

#include<algorithm>

using namespace std;

const int mod=1000;

int T,n,m;

struct Mat{

    int mat[40][40];

    Mat(){

	memset(mat,0,sizeof(mat));

    }

};

Mat mul(Mat A,Mat B){

    Mat C;

    for(int i=1;i<=n;i++){

        for(int j=1;j<=n;j++){

            for(int k=1;k<=n;k++){

                (C.mat[i][j]+=A.mat[i][k]*B.mat[k][j])%=mod;

            }

        }

    }

    return C;

}

Mat qpow(Mat A,int k) {

    Mat B;

    for(int i=1;i<=n;i++)

        B.mat[i][i]=1;

    while(k){

        if(k&1)

            B=mul(B,A);

        A=mul(A,A);

        k>>=1;

    }

    return B;

}

int main(){

    int s,t;

    while(1){

	scanf("%d%d",&n,&m);

	if(n==0&&m==0)return 0;

        Mat A,B;

        while(m--){

            scanf("%d%d",&s,&t);

            A.mat[++s][++t]=1;//因为不想从0开始循环就+1了

        }

        scanf("%d",&T);

        while (T--){

            int x,y,k;

            scanf("%d%d%d",&x,&y,&k);

            B=A;

            B=qpow(A,k);

            printf("%d\n",B.mat[++x][++y]);

        }

    }

    return 0;

}

巴特西