特別難調，洛谷題解區很多人代碼可讀性不強，做的我懷疑人生。

（雖然我的碼風也一般就是了）

---

前置知識：

Kruskal 求最小生成樹。

題面：

洛谷 P4208

兩種做法，一種矩陣樹一種枚舉。

（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) {   // 非連通圖，生成樹數量為0return 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++) {  //Kruskalint 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;
}