OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【SCOI2009】迷路

【题目描述】

windy在有向图中迷路了。 

该有向图有 N 个节点,windy从节点 0 出发,他必须恰好在 T 时刻到达节点 N-1。 

现在给出该有向图,你能告诉windy总共有多少种不同的路径吗? 

注意:windy不能在某个节点逗留,且通过某有向边的时间严格为给定的时间。

【输入】

第一行包含两个整数,N T。 

接下来有 N 行,每行一个长度为 N 的字符串。 

第i行第j列为'0'表示从节点i到节点j没有边。 

为'1'到'9'表示从节点i到节点j需要耗费的时间。

【输出】

一个整数,可能的路径数,这个数可能很大,只需输出这个数除以2009的余数。

【输入样例】

2 2

11

00

【输出样例】

1

【数据范围】

30%的数据,满足 2 <= N <= 5 ; 1 <= T <= 30 。 

100%的数据,满足 2 <= N <= 10 ; 1 <= T <= 1000000000 。

【题解】

关于邻接矩阵有一个神奇的性质,如果邻接矩阵中只有0/1代表两点是否连通,那么从s走到t且恰好经过k条边的方案总数,就是该邻接矩阵的k次幂中[s,t]的值。如果所有边权值都相同且为a,那么从s走到t且恰好走过总边权为k的路径的方案总数(a|k),即为该图邻接矩阵k/a次幂中[s,t]的值。

这道题图中的边权为1~9,所以考虑拆点,为了方便表示,把编号为i的点拆为i*10+1~i*10+9一共9个节点。如果i到j有一条权值为k的路径,那么就把矩阵中[i*10+k,j*10+1]的值设为1,相当于先从i*10+1→i*10+k走过k-1条长度为1的路径,再在i*10+k→j*10+1走过1条长度为1的路径,总长度为k。现在矩阵中只有0和1,计算这个矩阵的T次幂(矩阵快速幂优化),[1*10+1,n*10+1]的值即是方案总数。

记得多多取模,以免溢出!

【代码】

时间复杂度O(N^3*logT),这道题N和边权值的范围都比较小,为拆点提供了条件。

http://paste.ubuntu.com/7984110/

评论

© OI技术宅 | Powered by LOFTER