问题描述:
给定一张有向图邻接表,求任意点对间的路径数。
解题思路:
首先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;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int map[101][101];
vector < int > vec[101];
int n;
int dp[101][101];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int dfs(int start, int end)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int i, size = vec[start].size();
int sum = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(!map[start][end] && start != end)
return 0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(map[start][end] && map[end][start])
return -2;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(start == end)
return 1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 0; i < size; i++)
{
int u = vec[start][i];
if(map[u][start] && map[start][u])
return -2;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(dp[u][end] == -1)
dp[u][end] = dfs(u, end);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(dp[u][end] == -2)
return -2;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
sum += dp[u][end];
}
return sum;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int m, i, j, k, x, y;
int cas = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(scanf("%d", &m) != EOF)
{
memset(map, 0, sizeof(map));
for(i = 0; i < 101; i++)
vec[i].clear();
n = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(k = 0; k <= n; k++)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 0; i <= n; i++)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(j = 0; j <= n; j++)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(map[i][k] && map[k][j])
map[i][j] = 1;
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
memset(dp, -1, sizeof(dp));
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 0; i <= n; i++)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(j = 0; j <= n; j++)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(dp[i][j] == -1)
dp[i][j] = dfs(i, j);
}
}
printf("matrix for city %d\n", cas++);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 0; i <= n; i++)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(j = 0; j <= n; j++)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(i == j)
{
if(dp[i][j] == -2)
printf(" -1");
else
printf(" 0");
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
}else
{
if(dp[i][j] == -2)
printf(" -1");
else
printf(" %d", dp[i][j]);
}
}
puts("");
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
return 0;
}