问题描述：
给定一张有向图邻接表，求任意点对间的路径数。
解题思路：
首先floyed一遍，确定任意点对间是否可达，然后枚举点对进行记忆化搜索。具体思路就是如果i到k有边，k能够到达j，那么k到达j的路径数必定是i到j路径数的子集。枚举所有和i邻接的k即可。但是这道题目有可能有环，题目要求有环认为无穷路径，这样处理起来也是很方便的，可以这样想，如果i到k有边，但是k到j没有路径，那么即使k点存在一个环也对i到j的路径数没有任何影响，但是如果k有环，而且k可以到达j，那么i到j就必定有无穷多条路径了（因为可以在到达k的时候绕着环走啊走......），之后求出所有点对间的路径即可。
代码如下：
#include <iostream>
#include <vector>
using namespace std;
int map[101][101];
vector < int > vec[101];
int n;
int dp[101][101];
int dfs(int start, int end) 
{
int i, size = vec[start].size();
int sum = 0;
if(!map[start][end] && start != end)
return 0;
if(map[start][end] && map[end][start])
return -2;
if(start == end)
return 1;
for(i = 0; i < size; i++) {
int u = vec[start][i];
if(map[u][start] && map[start][u])
return -2;
if(dp[u][end] == -1)
dp[u][end] = dfs(u, end);
if(dp[u][end] == -2)
return -2;
sum += dp[u][end];
}
return sum;
}
int main(){
int m, i, j, k, x, y;
int cas = 0;
while(scanf("%d", &m) != EOF) {
memset(map, 0, sizeof(map));
for(i = 0; i < 101; i++)
vec[i].clear();
n = 0;
while(m--) {
scanf("%d %d", &x, &y);
map[x][y] = 1;
vec[x].push_back( y );
if(x > n) n = x;
if(y > n) n = y;
}
for(k = 0; k <= n; k++) {
for(i = 0; i <= n; i++) {
for(j = 0; j <= n; j++) {
if(map[i][k] && map[k][j])
map[i][j] = 1;
}
}
}
memset(dp, -1, sizeof(dp));
for(i = 0; i <= n; i++) {
for(j = 0; j <= n; j++) {
if(dp[i][j] == -1)
dp[i][j] = dfs(i, j);
}
}
printf("matrix for city %d\n", cas++);
for(i = 0; i <= n; i++) {
for(j = 0; j <= n; j++) {
if(i == j) {
if(dp[i][j] == -2)
printf(" -1");
else
printf(" 0");
}else {
if(dp[i][j] == -2)
printf(" -1");
else
printf(" %d", dp[i][j]);
}
}
puts("");
}
}
return 0;
}