|
|
## $VUA~125$ $Numbering$ $Paths$
|
|
|
|
|
|
[题目传送门](https://www.luogu.com.cn/problem/UVA125)
|
|
|
|
|
|
### 一、题目描述
|
|
|
给定一些组数据，每组数据由一个 $n$ 和 $n$ 对整数 $j$，$k$ 组成。由$EOF$停止读入。每组 $j_i，k_i$ 意味着存在一条由点 $j_i$到点 $k_i$的 **单向边**。其中，所有 $j_i，k_i$中的**最大值** $+1$ 即为 最终矩阵边长 $a$。可能存在 **自环**。数据保证任意一个点的入度和出度都不大于 $30$。
|
|
|
|
|
|
每组输出，包括一个字符串`matrix for city`，一个整数 $t$ 表示从 $0$ 开始的组数，以及一个 $a\times a$ 的矩阵 $M$，其中第 $i$ 行第 $j$ 个元素 $M[i][j]$ 表示从点 $i$ 到 $j$ 的**不同路径数量**。如果有无数条，在该位置输出 $-1$ 。**严格要求行末没有空格**。
|
|
|
|
|
|
### 二、题目解析
|
|
|
|
|
|
#### 前置芝士：$Floyd$
|
|
|
$Floyd$ 是一种求多源最短路的方法，其本质思想是动态规划。
|
|
|
|
|
|
设 $dp[i][j]$ 表示 $i$ 节点到 $j$ 节点之间的 **最短路**，那么可以得到状态转移方程：
|
|
|
$$\large dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])(1≤k≤n)$$
|
|
|
|
|
|
注意 $dp$ 时外层循环先枚举 $k$，因为 $Floyd$ 本来是一个三维 $dp$ （$dp[k][i][j]$ 表示 $i$ 节点到 $j$ 节点之间只能经过 $1 \sim k$ 这几个节点的最短路)，通过类似完全背包的空间优化才把空间复杂度降到二维。
|
|
|
|
|
|
**具体做法**
|
|
|
对于这道题，我们可以对状态转移方程进行修改。 设 $dp[i][j]$ 表示 $i$ 节点到 $j$ 节点之间的路径个数。同样的道理，我们需要枚举中间跳板 $k$。
|
|
|
|
|
|
显然，根据**乘法原理**， $i$ 节点到 $j$ 节点之间的路径个数 等于 $i$ 节点到 $k$ 节点之间的路径个数 与 $k$ 节点到 $j$ 节点之间的路径个数 **相乘**。
|
|
|
|
|
|
可以得到状态状态转移方程：
|
|
|
|
|
|
$$\large dp[i][j] = dp[i][j] + dp[i][k] \times dp[k][j](1 \le k \le n)$$
|
|
|
|
|
|
#### 怎么判断路径个数无数呢？
|
|
|
|
|
|
显然，路径个数无数当且只当图中有环时出现。当一个节点到达自己的路径数不是 $0$ 时，那么它就是图上环的一部分。
|
|
|
|
|
|
### 三、实现代码
|
|
|
```c++
|
|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 30;
|
|
|
int m, n, t;
|
|
|
int dp[N][N];
|
|
|
|
|
|
void floyd() {
|
|
|
for (int k = 0; k < n; k++)
|
|
|
for (int i = 0; i < n; i++)
|
|
|
for (int j = 0; j < n; j++)
|
|
|
dp[i][j] += dp[i][k] * dp[k][j]; //记录边数
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
while (scanf("%d", &m) != EOF) {
|
|
|
int a, b;
|
|
|
n = 0;
|
|
|
memset(dp, 0, sizeof(dp));
|
|
|
|
|
|
while (m--) {
|
|
|
scanf("%d%d", &a, &b);
|
|
|
dp[a][b] = 1; //单向边，同时边权为1
|
|
|
n = max({n, a, b}); //最大节点号
|
|
|
}
|
|
|
|
|
|
//注意有0节点，所以矩阵边长为n+1。
|
|
|
n++;
|
|
|
|
|
|
floyd();
|
|
|
|
|
|
printf("matrix for city %d\n", t++);
|
|
|
|
|
|
//结论：某个节点到自己的距离不为0，就是有环
|
|
|
for (int k = 0; k < n; k++)
|
|
|
if (dp[k][k]) { //如果存在环的话，需要特殊处理
|
|
|
for (int i = 0; i < n; i++)
|
|
|
for (int j = 0; j < n; j++)
|
|
|
if (dp[i][k] && dp[k][j]) //如果有其它点i,j利用过k，则i->k,k->j都是无数条路径
|
|
|
dp[i][j] = -1;
|
|
|
dp[k][k] = -1; //标识k->k也有无数条路径
|
|
|
}
|
|
|
|
|
|
//严格控制格式，输出矩阵
|
|
|
for (int i = 0; i < n; i++) {
|
|
|
for (int j = 0; j < n; j++)
|
|
|
if (j == 0)
|
|
|
printf("%d", dp[i][j]);
|
|
|
else
|
|
|
printf(" %d", dp[i][j]);
|
|
|
puts("");
|
|
|
}
|
|
|
}
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
