\(\color{#0066ff}{ 题目描述 }\)
现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。由于不同的最小生成树可能很多，所以你只需要输出方案数对31011的模就可以了。
\(\color{#0066ff}{输入格式}\)
第一行包含两个数，n和m，其中1<=n<=100; 1<=m<=1000; 表示该无向图的节点数和边数。每个节点用1~n的整数编号。
接下来的m行，每行包含两个整数：a, b, c，表示节点a, b之间的边的权值为c，其中1<=c<=1,000,000,000。
数据保证不会出现自回边和重边。注意：具有相同权值的边不会超过10条。
\(\color{#0066ff}{输出格式}\)
输出不同的最小生成树有多少个。你只需要输出数量对31011的模就可以了。
\(\color{#0066ff}{输入样例}\)
4 61 2 11 3 11 4 12 3 22 4 13 4 1\(\color{#0066ff}{输出样例}\)
8\(\color{#0066ff}{数据范围与提示}\)
说明 \(1<=n<=100; 1<=m<=1000;1\leq c_i\leq 10^9\)
\(\color{#0066ff}{题解}\)
MST有一些性质
每种权值的边的数量是固定的。
不同的生成树中，某一种权值的边任意加入需要的数量后，形成的联通块状态是一样的。
因此，我们枚举生成树中的边的权值，把所有权值不是当前权值的树边加入图中， 并缩点，以所有等于当前权值的边和缩完之后的点构造基尔霍夫矩阵，跑Matrix—Tree即可，最后答案乘法原理。
#include<bits/stdc++.h>#define LL long longLL in() { ???char ch; LL x = 0, f = 1; ???while(!isdigit(ch = getchar()))(ch == '-') && (f = -f); ???for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48)); ???return x * f;}const int maxn = 4040;const int mod = 31011;std::set<int> s, v, b;int fa[maxn], n, m, mp[maxn][maxn], choose[maxn], bel[maxn], ans = 1;struct node { ???int x, y, z; ???friend bool operator < (const node &a, const node &b) { return a.z < b.z; }}e[maxn];int findset(int x) { return x == fa[x]? fa[x] : fa[x] = findset(fa[x]); }void gauss(int tot) { ???for(int i = 1; i < tot; i++) { ???????for(int j = i + 1; j < tot; j++) { ???????????while(mp[j][i]) { ???????????????int now = mp[i][i] / mp[j][i]; ???????????????for(int k = i; k < tot; k++) mp[i][k] = (mp[i][k] - now * mp[j][k] + mod) % mod; ???????????????std::swap(mp[i], mp[j]); ???????????????ans = -ans; ???????????} ???????} ???????ans = (ans * mp[i][i]) % mod; ???} ???ans = ((ans % mod) + mod) % mod;}int main() { ???n = in(), m = in(); ???for(int i = 1; i <= m; i++) e[i].x = in(), e[i].y = in(), e[i].z = in(); ???std::sort(e + 1, e + m + 1); ???for(int i = 1; i <= n; i++) fa[i] = i; ???for(int i = 1; i <= m; i++) { ???????int xx = findset(e[i].x); ???????int yy = findset(e[i].y); ???????if(xx != yy) fa[xx] = yy, s.insert(e[i].z), b.insert(i); ???} ??????for(std::set<int>::iterator it = s.begin(); it != s.end(); it++) { ???????for(int i = 1; i <= n; i++) fa[i] = i; ???????for(int i = 1; i <= n; i++) ????????????for(int j = 1; j <= n; j++) ???????????????mp[i][j] = 0; ???????int tot = 0; ???????for(std::set<int>::iterator at = b.begin(); at != b.end(); at++) { ???????????if(e[*at].z == *it) continue; ???????????else { ???????????????int xx = findset(e[*at].x); ???????????????int yy = findset(e[*at].y); ???????????????if(xx != yy) fa[xx] = yy; ???????????} ???????} ???????v.clear(); ???????for(int i = 1; i <= n; i++) v.insert(findset(i)); ???????for(std::set<int>::iterator at = v.begin(); at != v.end(); at++) bel[*at] = ++tot; ???????for(int i = 1; i <= m; i++) { ???????????if(e[i].z != *it) continue; ???????????const node &now = e[i]; ???????????int xx = bel[findset(now.x)]; ???????????int yy = bel[findset(now.y)]; ???????????mp[xx][yy]--, mp[yy][xx]--, mp[xx][xx]++, mp[yy][yy]++; ???????} ???????gauss(tot); ???} ???printf("%d", ans); ???return 0;}P4208 [JSOI2008]最小生成树计数
原文地址：https://www.cnblogs.com/olinr/p/10425230.html