ZOJ (3497 Mistwald 关于矩阵求点直接连通的问题)

spoiler posted @ 2011年4月29日 15:48 in 十个利用矩阵乘法解决的经典题目 , 2075 阅读

题目大意:给你一个N*M 的矩阵, 矩阵里的每个点代表一个全送阵, 代表当前点可以全送到4个点,你的出发点是(1,1);要到达的点是(n,m),这里要注意的是,一旦任何点到了(n,m)点之后 就会被全送出去,离开整个地图,所以这里算是一个陷阱,您要把(n,m)点能够到达的点,全部置0,(”0“代表他不能到达某个点)

题目分析:

这里是Maxtrix67 大牛总结的 第八个矩阵的经典应用:

给定一个有向图,问从A点恰好走k步(允许重复经过边)到达B点的方案数mod p的值
把 给定的图转为邻接矩阵,即A(i,j)=1当且仅当存在一条边i->j。令C=A*A,那么C(i,j)=ΣA(i,k)*A(k,j),实际上就 等于从点i到点j恰好经过2条边的路径数(枚举k为中转点。类似地,C*A的第i行第j列就表示从i到j经过3条边的路径数。同理,如果要求经过k步的 路径数,我们只需要二分求出A^k即可;

题目让我们求的是他们是否连通,这里只需用1与0带入即可,

我们这里在乘的过程不是求和,而是用到“与”操作,因为我们要得出的结果不是路径数,而是 是否能经过K步到达该点~

代码+部分注释:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct M {
	int s[30][30];
};
struct M unit;
int n;
struct M multiply(struct M a,struct M b){
	struct M c;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			c.s[i][j]=0;
			for(int k=1;k<=n;k++)
                               //:注意下面这个操作,是“|”而不是“+”这里是求是否能到达
                               //而不是求 到达的路径数目!
				c.s[i][j]=(c.s[i][j]|a.s[i][k]*b.s[k][j]);
		}
	return c;
}
struct M paw(struct M a,int t){
	struct M ans=unit;
	struct M b=a;
	while(t){
		if(t%2==1)
			ans=multiply(ans,b);
		b=multiply(b,b);
		t/=2;
	}
	return ans;
}
int main(){
	struct M a;
	memset(unit.s,0,sizeof(unit.s));
	char str[100];
	int num[10];
	for(int i=1;i<=30;i++)
		unit.s[i][i]=1;
	int h,z,p,cas,t;
	int s,e,i,j,k;
	scanf("%d",&cas);
	while(cas--){
		memset(a.s,0,sizeof(a.s));
		scanf("%d %d",&h,&z);
		n=h*z;
		for(i=1;i<=h;i++)
			for(j=1;j<=z;j++){
				scanf("%s",str);
				sscanf(str,"((%d,%d),(%d,%d),(%d,%d),(%d,%d))",&num[1],&num[2],&num[3],&num[4],&num[5],&num[6],&num[7],&num[8]);
				s=(i-1)*z+j;
				for(k=1;k<=8;k+=2){
					e=(num[k]-1)*z+num[k+1];
					a.s[s][e]=1;
				}
			}
                //:转换成邻接矩阵后,a.s[n][]就是
              //代表原来地图里的[n][m]点与其他点的链接状态
              //因为题意说,凡是到了[n][m]点之后,就会马上
           //全送出去,离开这个地图,所以我们要把[n][m]到其他点的
           //状态值都赋为0!
		for(i=1;i<=n;i++)
			a.s[n][i]=0;
		scanf("%d",&p);
		while(p--){
			scanf("%d",&t);
			struct M  c=paw(a,t);
			if(c.s[1][n]==0)
				printf("False\n");
			else{   
				int x;
				for(x=1;x<=n;x++){
					if(c.s[1][x]==1)
						break;
				}
					if(n==x)
						printf("True\n");
					else
						printf("Maybe\n");
			}
		}
		printf("\n");
	}
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter