题目大意
给定一个 $n$ 个结点 $m$ 条边的带权无向图，所有边权都是正数。问图中有多少生成树，满足 $1$ 号点到每个点的最短路都等于在树上它到那个结点的距离。
数据范围：$n \le 50, m \le 1225$。
思路分析
我们发现这棵树一定是最短路 DAG 上的一棵生成树，于是我们建出最短路 DAG，再使用矩阵树定理求该 DAG 以 $1$ 为根的外向树个数即可。时间复杂度 $O(n^3)$。
然而这题的数据范围其实是可以出到 $n, m \le 10^6$ 的。我们发现最短路 DAG 有很好的性质。首先它一定是一个 DAG；其次，它入度为 $0$ 的点只有 $1$ 号结点。那么我们就可以给除了 $1$ 号点的每个点选一个父亲结点，然后把方案数相乘就可以得到答案。时间复杂度 $O(n \log n)$。
代码实现
1 | |
2 | |
3 | using namespace std; |
4 | |
5 | const int maxn = 50, inf = 1e9 + 1, mod = 1e9 + 7; |
6 | int n, a[maxn + 3][maxn + 3], f[maxn + 3][maxn + 3], deg[maxn + 3]; |
7 | |
8 | int main() { |
9 | scanf("%d", &n); |
10 | for (int i = 1; i <= n; i++) { |
11 | for (int j = 1; j <= n; j++) { |
12 | scanf("%1d", &a[i][j]); |
13 | if (i != j && a[i][j] == 0) { |
14 | a[i][j] = inf; |
15 | } |
16 | f[i][j] = a[i][j]; |
17 | } |
18 | } |
19 | for (int k = 1; k <= n; k++) { |
20 | for (int i = 1; i <= n; i++) { |
21 | for (int j = 1; j <= n; j++) { |
22 | f[i][j] = min(f[i][j], f[i][k] + f[k][j]); |
23 | } |
24 | } |
25 | } |
26 | for (int i = 1; i <= n; i++) { |
27 | for (int j = 1; j <= n; j++) { |
28 | if (i != j && f[1][i] + a[i][j] == f[1][j]) { |
29 | deg[j]++; |
30 | } |
31 | } |
32 | } |
33 | int ans = 1; |
34 | for (int i = 2; i <= n; i++) { |
35 | ans = 1ll * ans * deg[i] % mod; |
36 | } |
37 | printf("%d\n", ans); |
38 | return 0; |
39 | } |