记边权上限为 \(W\)。
转化一下即为 \((1, i)(i\in [2, n])\) 的边组成的也是原图的最小生成树。
考虑 \(\text{Prim}\) 的方法求最小生成树。
从 \(1\) 号点开始扩展,每次都会选取距离当前已扩展到的点最近的点 \(u\)。
为了保证 \((1, u)\) 的边在最小生成树中,需要满足对于已经扩展到的且不为 \(1\) 的点 \(v\),\(w_{(u, v)}\ge w_{(1, u)}\),因为否则 \((1, u)\) 对于 \((u, v)\) 就一定不优一定不会在最小生成树。
观察到这个就可以开始做了,考虑 \(\text{DP}\)。
令 \(f_{i, j}\) 为考虑了 \(1\sim i\) 的边权,除 \(1\) 外已经扩展了 \(j\) 个点的方案数。
转移考虑枚举当前边权 \(i\) 扩展了几个点出来,令其为 \(k\),那么 \(k\) 个点内部的边权需要 \(\ge i\),同时已经扩展且不为 \(1\) 的 \(j - k\) 个点与这 \(k\) 个点的边权需要 \(\ge i\),从原本剩下的 \(n - j\) 中选出 \(k\) 个点的方案数为 \(\binom{n - j}{k}\)。
所以 \(f_{i - 1, j - k}\) 对 \(f_{i, j}\) 的贡献的系数为 \(\binom{n - j}{k}\times (W - i + 1)^{\binom{k}{2} + k\times (j - k)}\),同时也可以不扩展,即 \(f_{i - 1, j}\) 对 \(f_{i, j}\) 的贡献的系数为 \(1\)。
初始值 \(f_{0, 0} = 1\),答案即为 \(f_{W, n - 1}\)。
时间复杂度 \(O(Wn^2\log n)\),可以预处理幂做到 \(O(Wn^2)\)。
#include<bits/stdc++.h>
using i64 = long long;
const i64 mod = 998244353;
inline i64 qpow(i64 a, i64 b) {
i64 v = 1;
while (b) b & 1 && ((v *= a) %= mod), (a *= a) %= mod, b >>= 1;
return v;
}
const int maxn = 250 + 10;
i64 C[maxn][maxn], f[maxn][maxn];
int main() {
int n, W; scanf("%d%d", &n, &W);
n--;
for (int i = 0; i <= n; i++) {
C[i][0] = 1;
for (int j = 1; j <= i; j++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
}
f[0][0] = 1;
for (int i = 1; i <= W; i++) for (int j = 0; j <= n; j++) {
f[i][j] = f[i - 1][j];
for (int k = 0; k < j; k++) (f[i][j] += f[i - 1][k] * C[n - k][j - k] % mod * qpow(W - i + 1, k * (j - k) + (j - k) * (j - k - 1) / 2)) %= mod;
}
printf("%lld\n", f[W][n]);
return 0;
}
标签:Star,个点,int,边权,1657E,扩展,Codeforces,i64,maxn
From: https://www.cnblogs.com/rizynvu/p/18015093