問題描述：
給定一張有向圖鄰接表，求任意點對間的路徑數(shù)。
解題思路：
首先floyed一遍，確定任意點對間是否可達，然后枚舉點對進行記憶化搜索。具體思路就是如果i到k有邊，k能夠到達j，那么k到達j的路徑數(shù)必定是i到j路徑數(shù)的子集。枚舉所有和i鄰接的k即可。但是這道題目有可能有環(huán)，題目要求有環(huán)認為無窮路徑，這樣處理起來也是很方便的，可以這樣想，如果i到k有邊，但是k到j沒有路徑，那么即使k點存在一個環(huán)也對i到j的路徑數(shù)沒有任何影響，但是如果k有環(huán)，而且k可以到達j，那么i到j就必定有無窮多條路徑了（因為可以在到達k的時候繞著環(huán)走啊走......），之后求出所有點對間的路徑即可。
代碼如下：
#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;
}