☆ [HDU2157] How many ways?? 「矩阵乘法求路径方案数」

传送门：>Here<

题意：给出一张有向图，问从点A到点B恰好经过k个点（包括终点）的路径方案数

解题思路

一道矩阵乘法的好题！妙哉~

话说把矩阵乘法放在图上好神奇，那么跟矩阵唯一有关的就是邻接矩阵……

考虑邻接矩阵在这道题里的含义也就是从A到B经过1个点的方案数——能到达或不能到达。而当邻接矩阵自乘时，假设自乘一次得到矩阵B，则$b[i][j] = \sum\limits_{}{}g[i][k]*g[k][j]$。因此k就作为了枚举的中介点，由于最后得到的项是累积的，所以自乘一次以后就得到了经过2个点的方案数。因此自乘k-1即能得到经过k个点的方案数。

此时，乘法的意义就成为了每一次累积$(i->k)的方案数 * (k->j)的方案数 \ （起点终点固定）$

Code

/*By DennyQi*/

#include <cstdio>

#include <queue>

#include <cstring>

#include <algorithm>

#define  r  read()

#define  Max(a,b)  (((a)>(b)) ? (a) : (b))

#define  Min(a,b)  (((a)<(b)) ? (a) : (b))

using namespace std;

typedef long long ll;

const int MAXN = ;

const int MAXM = ;

const int INF = ;

inline int read(){

    int x = ; int w = ; register int c = getchar();

    while(c ^ '-' && (c < '' || c > '')) c = getchar();

    if(c == '-') w = -, c = getchar();

    while(c >= '' && c <= '') x = (x << ) + (x << ) + c - '', c = getchar(); return x * w;

}

int N,M,K,Q,x,y,A,B;

int g[][],a[][],b[][],ans[][][];

inline void Init(){

    memset(g, , sizeof(g));

}

inline void Matrix_mul(){

    memset(ans, , sizeof(ans));

    for(int num = ; num <= ; ++num){

        for(int i = ; i <= N; ++i){

            ans[num][i][i] = ;

        }

    }

    for(int num = ; num <= ; ++num){

        for(int i = ; i <= N; ++i){

            for(int j = ; j <= N; ++j){

                b[i][j] = ;

                for(int k = ; k <= N; ++k){

                    b[i][j] = (b[i][j] + ans[num-][i][k] * g[k][j]) % ;

                }

            }

        }

        for(int i = ; i <= N; ++i){

            for(int j = ; j <= N; ++j){

                ans[num][i][j] = b[i][j];

            }

        }

    }

}

int main(){

    for(;;){

        N = r, M = r;

        if(!N && !M) break;

        Init();

        for(int i = ; i <= M; ++i){

            x = r+, y = r+;

            g[x][y] = ;

        }

        Matrix_mul();

        Q = r;

        while(Q--){

            A = r, B = r, K = r;

            printf("%d\n", ans[K][A+][B+] % );

        }

    }

    return ;

}

巴特西

☆ [HDU2157] How many ways?? 「矩阵乘法求路径方案数」

最新文章

热门文章