洛谷 P4208 Lutece 2726 最小生成树计数模版
22 April 2022 |
duanyll | Tags:
OI
题解
图论
题意
求 $n \leq 100$ 个节点, $m \leq 1000$ 条边的无向图的不同的最小生成树个数.
问题本身的性质
多尝试几个样例可以发现, 同一个图的所有最小生成树中, 相同边权的边的数量是一定相等的.
通过 Kruscal 算法的贪心过程容易证明这个结论: 从权值最小的边开始选择, 假如一种方案选择了 $k$ 条权值为 $w$ 的边, 若另一种方案选了比 $k$ 更多的 $w$ 边, 则说明原来的方案不是最优解; 若选了更少的 $w$ 边, 则新方案不是最优解. 因此, 满足最小的条件下, 生成树中相同权值的边数量相同.
借助以上性质, 可以先求出一棵最小生成树, 然后分别考虑生成树上不同权值的边的答案, 通过乘法原理得到结果. 然而, 直接用组合数计算是不行的, 因为任选 $k$ 条权值为 $w$ 的边, 不能保证仍然能够与其他权值的边组合成生成树.
通过矩阵树定理, 可以利用行列式计算图的所有生成树个数. 为了固定其余边权的边不变, 只考虑选取某个边权的边的情况, 可以通过并查集的方式将原有生成树上其他权值的边都缩成一点, 只保留要求权值的边, 则缩点后图的生成树数量就是满足条件的原图生成树数量.
矩阵树定理
定义图的 Laplacian 矩阵 $L\in Z^{n\times n}$,
\[L_{ij}= \begin{cases} \textrm{deg}(i), & i=j \\ -m_{ij}, & i\neq j \end{cases}\]其中 $\textrm{deg}(i)$ 是节点 i 的度数, $m_{ij}$ 是节点 u 和 v 的边数.
例如, 上图的 Laplacian 矩阵是
\[L= \begin{pmatrix} 3 & 0 & -1 & 0 & -1 & -1 \\ 0 & 2 & 0 & 0 & -1 & -1 \\ -1 & 0 & 3 & -1 & -1 & 0 \\ 0 & 0 & -1 & 1 & 0 & 0 \\ -1 & -1 & -1 & 0 & 4 & -1 \\ -1 & -1 & 0 & 0 & -1 & 3 \\ \end{pmatrix}\]则图的生成树个数为 $\det(L_0)$, 其中 $L_0$ 是 $L$ 去掉 $i$ 行 $i$ 列, $i$ 任取 $1 \leq i \leq n$.
详细的证明可参考 知乎文章.
行列式
显然不能用循环群定义和余子式定义直接求.
考虑高斯消元转换为上三角阵. 由于本题中模数不一定是质数, 不能直接进行除法 (疑似浮点数的精度可以通过此题), 但可以考虑用辗转相除法进行消元, 规避除法运算. 辗转相除法本身不会造成太高的复杂度, 仍可以视作 $O(n^3)$ 级别.
template <typename T>
T det(vector<vector<T>> a, T mod, int n = -1) {
T symbol = 1;
if (n == -1) n = a.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
while (a[i][i] != 0) {
T d = a[j][i] / a[i][i] % mod;
for (int k = i; k < n; k++) {
a[j][k] -= a[i][k] * d % mod;
a[j][k] = (a[j][k] % mod + mod) % mod;
}
swap(a[i], a[j]);
symbol = -symbol;
}
swap(a[i], a[j]);
symbol = -symbol;
}
}
T ans = symbol;
for (int i = 0; i < n; i++) {
ans *= a[i][i];
ans %= mod;
}
return (ans + mod) % mod;
}
代码
Kruscal 最小生成树已经将边排序过了, 枚举相同权值的边比较方便.
class kruskal {
struct edge {
int to, from;
int w;
edge(int to = 0, int from = 0, int w = 0) : to(to), from(from), w(w) {}
} e[MAXM * 2];
int ecnt;
int n;
int fa[MAXN];
int color[MAXN];
int find(int u) { return (fa[u] == u) ? u : fa[u] = find(fa[u]); }
static bool cmp(const edge& a, const edge& b) { return a.w < b.w; }
public:
kruskal(int n) {
this->n = n;
ecnt = 0;
}
void adde(int to, int from, int w) { e[++ecnt] = edge(to, from, w); }
int64 solve_count() {
sort(e + 1, e + ecnt + 1, cmp);
for (int i = 1; i <= n; i++) {
fa[i] = i;
}
int pos = 1;
int max_weight = 0;
vector<edge> tree_edges;
tree_edges.reserve(n - 1);
while (tree_edges.size() < n - 1 && pos <= ecnt) {
edge& now = e[pos];
pos++;
if (find(now.from) != find(now.to)) {
max_weight = now.w;
tree_edges.push_back(now);
fa[find(now.from)] = find(now.to);
}
}
if (tree_edges.size() < n - 1) return 0;
int64 ans = 1;
int cur_edge = 1;
while (cur_edge <= ecnt && e[cur_edge].w <= max_weight) {
int cur_weight = e[cur_edge].w;
for (int i = 1; i <= n; i++) {
fa[i] = i;
}
for (auto& e : tree_edges) {
if (e.w != cur_weight) {
fa[find(e.from)] = find(e.to);
}
}
int color_cnt = 0;
memset(color, -1, sizeof color);
for (int i = 1; i <= n; i++) {
if (color[find(i)] == -1) {
color[find(i)] = color_cnt;
color_cnt++;
}
color[i] = color[find(i)];
}
vector<vector<int64>> laplacian(color_cnt,
vector<int64>(color_cnt, 0));
while (e[cur_edge].w == cur_weight && cur_edge <= ecnt) {
int u = color[e[cur_edge].from];
int v = color[e[cur_edge].to];
laplacian[u][v] -= 1;
laplacian[v][u] -= 1;
laplacian[u][u] += 1;
laplacian[v][v] += 1;
cur_edge++;
}
ans *= det<int64>(laplacian, MOD, color_cnt - 1);
ans %= MOD;
}
return ans;
}
};