地址
点击打开链接
点击打开链接
这个题目，需要有一点性质了解，
邻接矩阵我认为可以把它叫做一步可达矩阵，也就是说我们建立一个邻接矩阵，可以直接用M[a][b]看出走一步就可以完成a到b的路线有多少条路线。然后如果将这个矩阵自乘一次就可以得到两步到达可以完成从a到b的路线有多少条路。
邻接矩阵我认为可以把它叫做一步可达矩阵，也就是说我们建立一个邻接矩阵，可以直接用M[a][b]看出走一步就可以完成a到b的路线有多少条路线。然后如果将这个矩阵自乘一次就可以得到两步到达可以完成从a到b的路线有多少条路。
知道上面的性质就可以正确解决这个题目，不过还有一些小的方面需要注意，比如t1不一定t2小，城市数的索引不一定在32之内，因此需要用到Map更改索引
代码：
#include<iostream>
#include<cstdio>
#include<string.h>
#include<stack>
#include<queue>
#include<queue>
#include<Map>
using namespace std ;
#define MAX 33
map<int,int> rem ;
int base =2008 ;
int num, n ;
struct Mat{
int M[MAX][MAX];
Mat(){
memset(M,0,sizeof(M));
}
void init()
{
int i ;
for (i = 0 ; i <MAX ; i ++)
M[i][i]=1;
}
void printf()
{
for(int i = 0 ; i <MAX ; i++)
{
for(int j = 0 ; j <MAX ; j++)
cout << M[i][j]<<" ";
cout <<endl;
}
}
}rms[10001];
Mat operator *(Mat a , Mat b )
{
int i , j ,k;
Mat c ;
for(k = 0 ; k < n ; k ++)
{
for(i = 0 ; i < n; i ++)
{
if(a.M[i][k]==0) continue ;
for(j = 0 ; j < n ; j++)
{
if(b.M[k][j]==0)continue ;
c.M[i][j] += (a.M[i][k]*b.M[k][j])%base;
c.M[i][j]%=base ;
}
}
}
return c ;
}
Mat operator ^(Mat a , int l)
{
Mat c ;
c.init();
while(l)
{
if(l%2== 1)
{
c = a*c ;
}
a = a*a ;
l>>=1;
}
return c ;
}
int main()
{
int num_roads,from,to;
while(scanf("%d",&num_roads)!=EOF)
{
rem.clear();
n = 0;
Mat a ;
while(num_roads--)
{
scanf("%d%d",&from,&to);
if(rem.count(from)==0)
{
rem[from]=n++;
}
if(rem.count(to)==0)
{
rem[to]=n++;
}
from = rem[from]; to = rem[to];
a.M[from][to]++;
}
rms[1]=a;
for(int i = 2 ; i <= 10000; i ++)
{
rms[i]=a*rms[i-1];
}
int queNum ,v1,v2,t1,t2;
scanf("%d",&queNum);
while(queNum--)
{
scanf("%d%d%d%d",&v1,&v2,&t1,&t2);
if(t1>t2||t2==0)
{
printf("%d\n",0);
continue ;
}
from =-1;
to = -1;
if(rem.count(v1)!=0)
from = rem[v1];
if(rem.count(v2)!=0)
to = rem[v2];
if(from==-1||to==-1)
{
printf("%d\n",0);
continue ;
}
int res = 0 ;
for(int i = t1 ; i <=t2 ; i ++)
{
res +=rms[i].M[from][to];
res %=base ;
}
printf("%d\n",res);
}
}
return 0 ;
}
版权声明：本文为qq_36616268原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。