luoguP4208 [JSOI2008]最小生成树计数 矩阵树定理

题目大意：

求最小生成树的数量

---

曾今的我感觉这题十分的不可做

然而今天看了看，好像是个类模板的题....

我们十分容易知道，记能出现在最小生成树中的边的集合为\(S\)

那么，只要是\(S\)中的边构成的树，一定能构成最小生成树

我们只要预处理哪些可能在最小生成树中即可

打个树剖维护以下就可以了

太懒了，不想打太长，然后就拿并查集随便弄了弄

最后来个矩阵树就行了

\(31011\)不是一个质数，用辗转相除法来消元

复杂度\(O(n^3 \log n)\)

---

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;#define ri register int
#define rep(io, st, ed) for(ri io = st; io <= ed; io ++)
#define drep(io, ed, st) for(ri io = ed; io >= st; io --)const int sid = 105;
const int mod = 31011;
inline void inc(int &a, int b) { a += b; if(a >= mod) a -= mod; }
inline void dec(int &a, int b) { a -= b; if(a < 0) a += mod; }
inline int mul(int a, int b) { return 1ll * a * b % mod; }int n, m, fa[sid];
int E[sid][sid];
struct edge {
int u, v, w;
friend bool operator < (edge a, edge b)
{ return a.w < b.w; }
} e[sid * 10];inline int find(int o) {
if(o == fa[o]) return o;
else return fa[o] = find(fa[o]);
}inline void init() {
sort(e + 1, e + m + 1);
rep(i, 1, n) fa[i] = i;
for(ri i = 1, j; i <= m; i = j + 1) {
j = i;
while(e[j].w == e[i].w) j ++; j --;
rep(k, i, j) {
int u = find(e[k].u), v = find(e[k].v);
if(u == v) continue;
inc(E[u][u], 1); inc(E[v][v], 1);
inc(E[u][v], mod - 1); inc(E[v][u], mod - 1);
}
rep(k, i, j) {
int u = find(e[k].u), v = find(e[k].v);
if(u == v) continue; fa[u] = v;
}
}
}inline void calc() {
int sign = 1;
n --;
rep(i, 1, n) rep(j, i + 1, n)
while(E[j][i]) {
int t = E[i][i] / E[j][i];
rep(k, i, n) dec(E[i][k], mul(t, E[j][k]));
swap(E[j], E[i]);
sign *= -1;
}
int ans = 1;
rep(i, 1, n) ans = mul(ans, E[i][i]);
if(sign == 1) printf("%d\n", ans);
else printf("%d\n", mod - ans);
}int main() {
cin >> n >> m;
for(int i = 1; i <= m; i ++)
cin >> e[i].u >> e[i].v >> e[i].w;
init(); calc();
return 0;
}