链接矩阵快速幂（zoj3497）

这题每个点可以到都有4个链接点。关键是最后那个点到其他节点的传送是假的，没用的。因为题意说明一旦到了最后那个节点就会走出谜之森林，所以该点到其他点的链接矩阵值都。。.附代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n;

struct matrix
{
    int f[50][50];
};

matrix pow(matrix a,matrix b)
{
    int i,j,k;
    matrix c;
    memset(c.f,0,sizeof(c.f));
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            for(k=1;k<=n;k++)
                if(a.f[i][k]==1&&b.f[k][j]==1)
                    c.f[i][j]=1;
    return c;
}
matrix quick_pow(matrix a,int k)
{
    matrix s;
    memset(s.f,0,sizeof(s.f));
    int i;
    for(i=1;i<=n;i++) s.f[i][i]=1;
    while(k){
        if(k&1)
            s=pow(s,a);
        a=pow(a,a);
        k=k>>1;
    }
    return s;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        int a,b,i,j;
        scanf("%d%d",&a,&b);
        getchar();
        n=a*b;
        struct matrix s;
        memset(s.f,0,sizeof(s.f));

        for(i=1;i<=a;i++){

            for(j=1;j<=b;j++){
             getchar();
                int uu=4;
                while(uu--){
                int x,y;
                scanf("(%d,%d)",&x,&y);
                getchar();
                if((i-1)*b+j==n) continue;
                s.f[(i-1)*b+j][(x-1)*b+y]=1;

                }
                 getchar();
            }

        }
        //for(i=1;i<=n;i++) s.f[n][i]=0;
        int m;
        scanf("%d",&m);
        while(m--){
            int k;
            scanf("%d",&k);
            struct matrix temps=quick_pow(s,k);
            int flag=1;
            if(temps.f[1][n]==0) printf("False\n");
            else if(temps.f[1][n]>0){
                for(i=1;i<n;i++){
                    if(temps.f[1][i]>0){
                        printf("Maybe\n");
                        flag=0;
                        break;
                    }
                }
                if(flag==1) printf("True\n");
            }
        }
        printf("\n");
    }
}

链接矩阵快速幂（zoj3497）,布布扣,bubuko.com

链接矩阵快速幂（zoj3497）

原文：http://blog.csdn.net/fei____fei/article/details/20551249