题解 P4208 【[JSOI2008]最小生成树计数】
ShuYuMo
2020-09-11 10:53:56
### P4208 [JSOI2008]最小生成树计数
#### 应该了解到的：
- 对于一张没有相同边权的图 $G$ 来说，他的最小生成树是唯一的。换句话说，导致图 $G$ 的最小生成树 $T$ 不唯一的因素是边权重复的边。对应 `kruskal` 的运行过程来说，就是在边排序的过程中，相同权值的边内部的处理顺序。
- 尽管相同权值的边处理顺序不同，但是不管按什么顺序处理这些边，最终处理完这种权值的边后，图的联通关系是相同的。
- 因为对于边权相同的边处理顺序并不影响后面比这些边大的边的决策情况。所以 每一组权值相同的边对答案的贡献是独立的。可以分别考虑每一组权值相同的边 对答案的贡献，最终乘法原理统计即可。
#### 两种解法：
- 对于每一组权值相同的边，考虑其贡献的方法
- 暴力枚举每一组边
- 关于其他题解的另一种方法是：
- 例如 当前计算贡献的一组具有相同边权的边，先将与其权值**不同**的边加入图中，形成一堆连通块，每一个连通块缩成一个点，再加入这组边，对形成的图做生成树计数，然后这张图的生成树个数就是这组边对答案的贡献。
- 而我想到的是：
- 如果考虑 `kruskal` 的运行过程，对于一组具有相同权值的边，其贡献的计算方法应该是加入比这组边的边权**小**的所有边，形成连通块 缩点，再加入这组边，对形成的图 通过矩阵树定理 求生成树计数。
#### 两种解法的异同
- 必须是加入除了选定的那一组以外**全部**的边之后，对每个联通块缩点，再加入选定的那一组边权相同的边，统计生成树计数，即这组点的贡献。
- 因为如果只加入比这组边的边权小的边，可能这张图并不联通，也就是说，如果用矩阵树定理求其生成树的数量，答案将会是 $0$。
- 暴力算法可以求出只加入比这组边的边权小的边后，按照不同顺序加入当前这组边后形成的森林数量，而矩阵树定理只能求出生成树数量。
- 所以如果使用矩阵树定理求每组边贡献，必须加入这组之外的全部边后才能计数。
- 可以证明，加入部分边，求下一组边按不同顺序加入求其森林数 和 加入除这组边以外的所有边后求联通生成树数 这两种方法是等价的。只不过求森林数没有什么多项式解法，不能像求生成树数量那样用矩阵树定理优化复杂度。
#### 具体实现方法
可以考虑先建出一棵最小生成树，然后考虑某组权值为 $w$ 的边时，`dfs` 求出删去这条边后 所有连通块，对所有连通块缩点，然后用 `Matrix-tree` 求出这一组边加入后的图形成的生成树数量。
#### 代码
```cpp
#include <climits>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <algorithm>
int read() { int x; scanf("%d", &x); return x; }
using namespace std;
const int _N = 2e2 + 10;
const int _M = 2e3 + 10;
const int MOD = 31011;
int n, m;
struct edges{
int u, v, w;
}edge[_M];
bool CMP(const edges & A, const edges & B) { return A.w < B.w; }
namespace Tree{
int head[_N];
struct edges{
int node;
int w;
int nxt;
}edge[_M];
int tot = 0;
void add(int u, int v, int w) {
tot++;
edge[tot].node = v;
edge[tot].nxt = head[u];
edge[tot].w = w;
head[u] = tot;
}
int nodetot = 0;
int SCC[_N]; // 这里的SCC命名并不严谨，这里的SCC只是指缩点后，某个原图点所在的缩点编号。如 SCC[i] 表示原图中的点 i 缩入的点。
void dfs(int now, int W){
SCC[now] = nodetot;
for(int i = head[now]; i ;i = edge[i].nxt) {
int ex = edge[i].node;
if(SCC[ex]) continue; if(edge[i].w == W) continue;
dfs(ex, W);
}
}
void initDfs(int x) {
nodetot = 0;
fill(SCC + 1, SCC + 1 + n, 0);
for(int i = 1; i <= n; i++){
if(!SCC[i]) ++nodetot, dfs(i, x);
}
}
} using Tree::add; using Tree::nodetot; using Tree::SCC; using Tree::initDfs;
int fa[_N];
void init(int n) { for(int i = 1; i <= n; i++) fa[i] = i; }
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void merge(int x, int y) { x = find(x); y = find(y); fa[x] = y; }
bool ask(int x, int y) { return find(x) == find(y); }
int matrix[_N][_N];
int det(int n){
int ans = 1;
for(int i = 1; i <= n; i++) {
for(int j = i + 1; j <= n; j++) {
while(matrix[j][i]) {
int x = matrix[i][i] / matrix[j][i];
for(int k = i; k <= n; k++){
matrix[i][k] = (matrix[i][k] -0ll- (matrix[j][k] *1ll* x % MOD) + MOD) % MOD;
swap(matrix[i][k], matrix[j][k]);
} ans *= -1;
}
}
}
for(int i = 1; i <= n; i++) ans = (ans *1ll* matrix[i][i]) % MOD;
return ( ans % MOD + MOD ) % MOD;
}
int main(){
n = read(), m = read();
for(int i = 1; i <= m; i++) {
edge[i].u = read();
edge[i].v = read();
edge[i].w = read();
}
init(n);
sort(edge + 1, edge + 1 + m, CMP);
for(int i = 1; i <= m; i++) {
edges &now = edge[i];
if(ask(now.u, now.v)) continue;
add(now.u, now.v, now.w); add(now.v, now.u, now.w);
merge(now.u, now.v);
}
int ans = 1; edge[m + 1].w = INT_MAX;
for(int i = 1; i <= m; i++) {
int L = i, R;
for(R = i; edge[R + 1].w == edge[L].w; R++);
cerr << L << " " << R << " " << edge[L].w << endl;
initDfs(edge[L].w);
for(int j = L; j <= R; j++) {
edges &now = edge[j];
matrix[ SCC[now.u] ][ SCC[now.u] ] ++;
matrix[ SCC[now.v] ][ SCC[now.v] ] ++;
matrix[ SCC[now.u] ][ SCC[now.v] ] --;
matrix[ SCC[now.v] ][ SCC[now.u] ] --;
}
ans = (ans *1ll* det(nodetot - 1)) % MOD;
for(int k = 1; k <= nodetot; k++) for(int j = 1; j <= nodetot; j++) matrix[k][j] = 0;
i = R;
}
printf("%d\n", ans);
return 0;
}
```