黑暗城堡
题意
给出一张 \(n\) 个点 \(m\) 条边的图，求该图有多少棵生成树满足生成树上每个点 \(x\) 到 \(1\) 的最短距离 \(S_x\) 等于原图 \(x\) 到 \(1\) 的最短距离 \(D_x\)，答案 \(\bmod 2^{31}-1\)。
思路
先考虑如何求出一棵满足条件的生成树。
令 \(1\) 为这棵生成树的根，容易发现对于 \(x\) 的儿子 \(y\)，记 \(d_x\) 为 \(1\) 到 \(x\) 的距离，\((x,y)\) 为 \(x\) 到 \(y\) 的距离，有 \(d_y=d_x+(x,y)\)。
先以 \(1\) 为源点求一遍单源最短路，再从 \(1\) 开始遍历整张图，每次选出合法的后继点作为自己的儿子。
再考虑如何求出所有符合条件的生成树。
我们先随意求出一棵合法生成树，再在这棵生成树上计数。
记 \(f_x\) 为以 \(x\) 为根的子树可以变为多少种合法树，\(c_x\) 为 \(x\) 有多少个合法的爹，即满足 \(d_x=d_y+c(x,y)\) 的 \(y\) 的个数，有：
\[f_x=\prod_{y \in son_x} f_y \times c_y \]即每个儿子可以随意换爸爸，每个儿子相互独立，乘起来就行。
答案为 \(f_1\)，时间复杂度：\(O(n^2)\)。
代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 1e6 + 5;
const LL mod = (1ll << 31) - 1;
int tot, head[N], nxt[N << 1];
int ver[N << 1], edge[N << 1];
int n, m, dis[N];
bool vis[N];
LL f[N];
void add(int u, int v, int w) {
ver[++ tot] = v;
nxt[tot] = head[u];
head[u] = tot;
edge[tot] = w;
}
struct node {
int d, id;
};
bool operator < (node x, node y) {
return x.d > y.d;
}
void dijkstra() {
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
dis[1] = 0;
priority_queue <node> Q;
Q.push({0, 1});
while (!Q.empty()) {
int x = Q.top().id; Q.pop();
if (vis[x]) continue;
vis[x] = 1;
for (int i = head[x]; i; i = nxt[i]) {
int y = ver[i], z = edge[i];
if (dis[y] > dis[x] + z) {
dis[y] = dis[x] + z;
Q.push({dis[y], y});
}
}
}
memset(vis, 0, sizeof(vis));
}
void dfs(int x) {
vis[x] = 1, f[x] = 1;
for (int i = head[x]; i; i = nxt[i]) {
int y = ver[i], z = edge[i];
if (vis[y]) continue;
if (dis[y] != dis[x] + z) continue;
dfs(y);
LL cnt = 0;
for (int j = head[y]; j; j = nxt[j])
if (dis[ver[j]] + edge[j] == dis[y])
cnt ++;
f[x] *= f[y] * cnt % mod;
f[x] %= mod;
}
}
int main() {
freopen("dark.in", "r", stdin);
freopen("dark.out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= m; i ++) {
int u, v, w;
cin >> u >> v >> w;
add(u, v, w);
add(v, u, w);
}
dijkstra();
dfs(1);
cout << f[1] << "\n";
return 0;
}