Description
Bruce是K国的商人，他在A州成立了自己的公司，这次他的公司生产出了一批性能很好的产品，准备宣传活动开始后的第L天到达B州进行新品拍卖，期间Bruce打算将产品拿到各个州去做推销宣传,以增加其影响力。
K国有很多个州,每个州都与其他一些州相邻,但是K国对商人作宣传却有一些很奇怪的规定：
1、 商人只能从某些州到达另外一些州，即连通路线是单向的，而且有些州可能是到达不了的。
2、 商人不允许在同一个州连续宣传两天或以上，每天宣传完必须离开该州。
3、 商人可以多次来到同一个州进行宣传。
"我必须找出一条影响力最大的路线才行"，Bruce想，"但我首先必须知道到底有多少这种符合规定的宣传路线可供我选择。"现在Bruce把任务交给了你。并且出于考虑以后的需要，你还要帮他算出给出的两州之间的路线的总数。
Input
输入文件第一行包含三个整数n,m,L（1≤n,L≤100），分别表示K国的州数、连通路线的数量，以及多少天后必须到达B州。接下来有m行，每行一队整数x,y（1≤x,y≤n），表示商人能从x州到达y州。
第m+2行为一个整数q（1≤q≤100），表示Bruce有q个询问。下面q行每行两个整数A,B（1≤A,B≤n），即A、B州的位置。
Output
输出文件包含q行，每行一个整数t，为所求的从A州到B州满足上述规定的路线总数。
输入数据中的询问将保证答案t在长整数范围内，即t<231。
Sample Input
4 5 6 1 2 2 3 3 4 4 1 2 4 2 1 4 4 2
Sample Output
2 1
1. 原题中文大意.
商人的宣传即是一个有向图的问题。有一个有向图。该图的每条件权重一样，从图中任意一点a刚好通过L步到达另一点b有多少条路线。
2. 算法思想及解题思路.
使用了动态规划算法。令 dp[num][dest] 表示从起点通过 num 条边到达终点共有多少种走法。
先由已经知条件易得从起点通过一条它的邻接边到达它的所有邻接点共有一条路线。即 dp[1][邻接点] 易求得。而 dp[x][y] = sum( dp[x-1][可以一条邻接边到达y的点] )。
3. 主要数数据结构.
主要数据结构为三个数组。这本个数组都不用下标为0的元素。
char odgree[MAX_VERTICES_NUM+1];
下标为每个顶点的编号.表示每个顶点的出度.
int routine[MAX_VERTICES_NUM+1][MAX_VERTICES_NUM+1];
‘路由表’ routine[x][n] = y 表示从顶点x经它的第n条邻接边可以到达顶点y.
int dp[MAX_VERTICES_NUM+1][MAX_VERTICES_NUM+1];
这个数组即第二节提到的dp数组，dp[L][x] = num从起点开始经L条边走到顶点 x 共有 num 种走法。
4. 逐步求精算法描述（含过程及变量说明）;
从已知条件初始化 odgree 和 routine 数组.
bzero(odgree, sizeof(odegree));
for(int x,y, i = 0; i < m; i++)
{
scanf("%d %d", &x, &y);
odgree[x]++;
routine[x][ odgree[x] ] = y;
}
下面的cal函数输入起点顶点和终点顶点，返回共有多少种走法。
int cal(char start, char dest)
{
memset(dp, 0, sizeof(dp));
for ( int i = 1; i <= odgree[start]; i++ ) // 遍历起点的每一条邻接边
{
dp[1][ routine[start][i] ]++; // 初始时经过一邻接边到达别一点的走法有几种.
}
for ( int i = 2; i <= L; i++ ) // 一直走到第L步.
{
for ( int j = 1; j <= n; j++ ) // 遍历每一个顶点.
{
for ( int k = 1; k <= odgree[j]; k++ ) // 该顶点的第一条邻接边
{
// 上文提到的递推公式。
dp[i][ routine[j][k] ] += dp[i-1][j];
}
}
}
return dp[L][dest]; // 返回结果
}
5. 程序注释清单
#include <cstdio>
#include <cstdlib>
#include <memory>
#include <cstring>
#include <vector>
using namespace std;
const int MAX_VERTICES_NUM = 100; // 最多多少个顶点.
int n, m, L, q; // 实际n个点、m条边，L 为期限.q为有多少个询问.
static char odgree[MAX_VERTICES_NUM+1]; // 记每个点的出度.不用下标为0的元素.
static int routine[MAX_VERTICES_NUM+1][MAX_VERTICES_NUM+1]; // table[x][y] 表示x点经它的第y条边可以去到哪个点.
static int dp[MAX_VERTICES_NUM+1][MAX_VERTICES_NUM+1]; // dp[x][y] 表示经x条边，可以从某点到 y 点.
int cal(char start, char dest)
{
memset(dp, 0, sizeof(dp));
for ( int i = 1; i <= odgree[start]; i++ ) // 遍历起点的每一条邻接边.
{
dp[1][ routine[start][i] ]++; // 初始时经过一步到达别一点的走法.
}
for ( int i = 2; i <= L; i++ ) // 一直走到第 L 步.
{
for ( int j = 1; j <= n; j++ ) // 遍历每一个点.
{
for ( int k = 1; k <= odgree[j]; k++ ) // 该点的每一个邻接点.
{
dp[i][ routine[j][k] ] += dp[i-1][j];
}
}
}
return dp[L][dest];
}
int main(int argc, char* argv[])
{
while ( EOF != scanf("%d %d %d", &n, &m, &L) )
{
memset(odgree, 0, sizeof(odgree));
for(int x,y, i = 0; i < m; i++)
{
scanf("%d %d", &x, &y);
odgree[x]++;
routine[x][ odgree[x] ] = y;
}
scanf("%d", &q);
vector<int> results;
for ( int start,dest, i = 0; i < q; i++)
{
scanf("%d %d", &start, &dest);
results.push_back(cal(start, dest));
}
for ( int i = 0; i < results.size(); i++ )
{
printf("%d\n", results[i]);
}
}
return 0;
}
6. 测试数据
4 5 6
1 2
2 3
3 4
4 1
2 4
5
1 4
4 2
2 1
1 3
3 4
2
1
2
1
0
7. 对时间复杂度，空间复杂度方面的分析、估算及程序优化的分析和改进.
本解决方法的时间复杂度为O(L*n*n)，空间复杂度为O(n*n).
用动态规划解此题的时间复杂度优于用邻接矩阵表示图然后用图的乘法解出。后者的时间复杂志为O(L*n*n*n)。