学步园

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=2157

题目大意: 给出有向连通图，求A到B恰好经过K个点的方案数%m

解题思路: 邻接矩阵0-1存储边edge[ ][ ]

                    邻接矩阵相乘，edge[i][k]*edge[k][j]当且仅当edge[i][k]和edge[k][j]同时为1，也就是同时存在这两条边时相乘才为1

                    定义G[i][j]m表示i到j恰好经过m条边的方案数，则方程: 

                                            G[i][j]m=ΣG[i][k]m-1*edge[k][j](1<=k<=n) 
                

                        利用二进制的思想把m次计算简化成log m次运算

代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INF 0x3f3f3f3f
#define MAX 110

typedef struct node{
	int edge[MAX][MAX];
}matrix;

matrix map,map2,ant,temp;
int n,mm=1000;

matrix Matrix(matrix &a,matrix &b)
{
	int i,j,k;
	memset(temp.edge,0,sizeof(temp.edge));  //temp初始化为0
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			for(k=0;k<n;k++)
				temp.edge[i][j]=(temp.edge[i][j]+a.edge[i][k]*b.edge[k][j]%mm);  //乘积%mm
	return temp;
}

int Find(int s,int e,int k)  //快速幂的思想
{
	while(k)
	{
		if(k%2)
			ant=Matrix(map2,ant);
		map2=Matrix(map2,map2);
		k>>=1;
	}
	return ant.edge[s][e];
}

int main()
{
	int i,j,m,t,a1,a2,s,e,k;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		if(n==0&&m==0)
			return 0;
		memset(map.edge,0,sizeof(map.edge));
		for(i=0;i<m;i++)
		{
			scanf("%d%d",&a1,&a2);
			map.edge[a1][a2]=1;         //单向边
		}
		scanf("%d",&t);
		while(t--)
		{
			memset(ant.edge,0,sizeof(ant.edge));   //ant初始化为单位矩阵
			for(i=0;i<n;i++)
				for(j=0;j<n;j++)
					map2.edge[i][j]=map.edge[i][j];
			for(i=0;i<n;i++)
				ant.edge[i][i]=1;
			scanf("%d%d%d",&s,&e,&k);
			printf("%d\n",Find(s,e,k)%mm);
		}
	}
	return 0;
}

注:原创文章，转载请注明出处