特别难调，洛谷题解区很多人代码可读性不强，做的我怀疑人生。
（虽然我的码风也一般就是了）
前置知识：
题面：
两种做法，一种矩阵树一种枚举。
（1）矩阵树定理
都知道矩阵树定理能算生成树个数，但本题要求最小生成树个数，不能直接使用。
观察发现：
同一无向连通图中，不同最小生成树各个权值的边的数量是相同的。
简单证明下：
如果存在两个最小生成树，一个选了 和
这两条边，
一个选了 和
，其他边都相同。
其中 的权值小于
，而且两对边的权值和相同。
那我们就肯定可以选 和
，这样能得出更小的生成树，矛盾。
（肯定有人会问：你怎么能假定俩生成树其他边一样呢，难到不能通过其他边到这四个点吗？
笨，要是能到值还更小，那一开始不就选了吗）
我们考虑先用 Kruskal 算法求出最小生成树的边集。
对于权值为 i 的边，把边集里其他权值不为 i 的边加到图里，用并查集缩点。
（因为每个权值的边能减少的连通块数量是固定的，只加最小生成树里的就好。
绝对不能把边集里所有权值不为 i 的边一股脑全加进去！！那样出来的就不是最小生成树了！）
而边集里所有权值为 i 的边加到基尔霍夫矩阵里，在缩点的图上求生成树数量。
（这个时候求生成树就保证选的 i 权值边的数量和一开始求最小生成树 i 权值边的数量一致！）
最后再把每个行列式乘到一起，就是答案。
时间复杂度：
（M 是总边数）
代码思路不难，难的是调试，注意细节，别打错了。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e3 + 10;
const LL P = 31011;
int fa[N];
int findfa(int x) { //并查集路径压缩
if(fa[x] == x) {
return x;
}
return fa[x] = findfa(fa[x]);
}
struct node {
int x, y;
LL c;
} a[N];
bool cmp(node na, node nb) {
return na.c < nb.c;
}
LL L[N][N]; //基尔霍夫/拉普拉斯矩阵
void add(int x, int y) {
L[x][y] --; L[y][x] --;
L[x][x] ++; L[y][y] ++;
}
int n, m;
LL gauss(int nn) { //高斯消元求行列式
nn--;
int r = 1;
LL res = 1;
for (int c = 1; c <= nn; c++) {
for (int i = r + 1; i <= nn; i++) {
while (L[i][c]) {
LL bs = L[r][c] / L[i][c];
for (int j = 1; j <= nn; j++) {
L[r][j] -= L[i][j] * bs;
}
swap(L[r], L[i]);
res *= -1;
}
}
if (L[r][c] != 0) {
r ++;
}
}
if (r <= nn) { // 非连通图，生成树数量为0
return 0;
}
for (int i = 1; i <= nn; i++) {
res = res * L[i][i] %P;
}
return res;
}
map<LL, LL> mp; //用来判断这条边的权值在不在最小生成树边集里
int b[N], e[N]; //b：缩点后点的编号，e：最小生成树边集
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> a[i].x >> a[i].y >> a[i].c;
}
for (int i = 1; i <= n; i++) { //并查集初始化
fa[i] = i;
}
int len = 0;
sort (a + 1, a + m + 1, cmp);
for (int i = 1; i <= m; i++) { //先跑一遍 Kruskal
int tx = findfa(a[i].x);
int ty = findfa(a[i].y);
if (tx != ty) {
mp[a[i].c] = 1;
fa[tx] = ty;
e[++len] = i;
}
}
LL ans = 1;
for (int i = 1; i <= len; i++) if(mp[a[e[i]].c]) {
for (int j = 1; j <= n; j++) {
fa[j] = j; //再初始化一编，因为除了权值为 a[e[i]].c 边还要跑一遍缩点
}
for (int j = 1; j <= len; j++) {
if(a[e[j]].c != a[e[i]].c) {
int tx = findfa(a[e[j]].x);
int ty = findfa(a[e[j]].y);
if (tx != ty) {
fa[tx] = ty;
}
}
}
int tmp = 0; //缩点后有几个点
for (int j = 1; j <= n; j++) if (findfa(j) == j) {
tmp ++;
b[j] = tmp;
}
memset(L, 0, sizeof(L));
for (int j = 1; j <= m; j++) {
if(a[j].c == a[e[i]].c) {
int tx = findfa(a[j].x);
int ty = findfa(a[j].y);
if(b[tx] != b[ty]) { //不在一个连通块里
add(b[tx], b[ty]); //加到基尔霍夫矩阵里
}
}
else if(a[j-1].c == a[e[i]].c){
break; //边集已经排过序，可以直接退出
}
}
ans = ans * gauss(tmp) %P; //乘法原理行列式
mp[a[e[i]].c] = 0; //遍历过就等于 0
}
cout << ans << "\n";
return 0;
}（2）dfs 枚举
首先还是 Kruskal 算法确定最小生成树，并统计每种权值的数量。
对于每种权值，深搜枚举该权值的边是否选择，最终返回可行方案数。
将所有权值的方案数相乘，得到总的最小生成树数量。
时间复杂度：
（M 是总边数，N 是点数）
直接看代码吧，我写了注释：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e3 + 10;
const LL P = 31011;
struct node{
int x, y;
LL c;
} a[N];
bool cmp(node na, node nb) {
return na.c < nb.c;
}
map<LL, LL> mp; //存边权对应离散值的
int n, m;
int fa[N];
int findfa(int x) { //并查集
if (fa[x] == x) {
return fa[x];
}
return fa[x] = findfa(fa[x]);
}
LL num[N], res;
void dfs(int now, int cnt, LL nowc) { //now：当前节点，cnt：当前权值选了几条边，nowc：当前权值
if (cnt == num[mp[nowc]]) { //选够了就退出
res = (res + 1) %P;
return ;
}
if (a[now].c != nowc) { //越界了，选到别的权值区域
return ;
}
int pre[N]; //存档 fa数组，一定一定要在函数内定义！！不然迭代之前的数据就不见了
for (int i = 1; i <= n; i++) {
pre[i] = fa[i];
}
int tx = findfa(a[now].x);
int ty = findfa(a[now].y);
if (tx != ty) {
fa[tx] = ty;
dfs(now + 1, cnt + 1, nowc); //把当前边加进去
}
for (int i = 1; i <= n; i++) {
fa[i] = pre[i];
}
dfs(now + 1, cnt, nowc); //不加当前边
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
int len = 0;
for (int i=1 ; i <= m; i++) {
cin >> a[i].x >> a[i].y >> a[i].c;
if (!mp[a[i].c]) {
len ++;
mp[a[i].c] = len; //边权离散值
}
}
sort(a + 1, a + m + 1, cmp);
for (int i = 1; i <= n; i++) {
fa[i] = i; //并查集初始化
}
int sum = 0;
memset (num, 0, sizeof(num));
for (int i = 1; i <= m; i++) { //Kruskal
int tx = findfa(a[i].x);
int ty = findfa(a[i].y);
if (tx != ty) {
sum ++;
num[mp[a[i].c]] ++;
fa[tx] = ty;
}
}
if (sum < n - 1) {
cout << "0" << "\n";
return 0;
}
for (int i = 1; i <= n; i++) {
fa[i] = i; //再来
}
LL ans = 1;
for (int i = 1; i <= m; i++) if(mp[a[i].c]) { //还没被 dfs过的最小生成树权值
res = 0;
dfs(i, 0, a[i].c);
ans = ans * res %P;
for (int j = i; j <= m; j++) {
if (a[j].c == a[i].c) { //把当前权值的边都加进去
int tx = findfa(a[j].x);
int ty = findfa(a[j].y);
if (tx != ty) {
fa[tx] = ty;
}
}
else if (a[j - 1].c == a[i].c) { //越界
break;
}
}
mp[a[i].c] = 0; //dfs过了当前权值，之后就不用了
}
cout << ans << "\n";
return 0;
}