无向图生成树计数（Matrix-Tree）
对于生成树的计数，一般采用矩阵树定理(Matrix-Tree 定理)来解决。
Matrix-Tree 定理的内容为：对于已经得出的基尔霍夫矩阵，去掉其随意一行一列得出的矩阵的行列式，其绝对值为生成树的个数
因此，对于给定的图 G，若要求其生成树个数，可以先求其基尔霍夫矩阵，然后随意取其任意一个 n-1 阶行列式，然后求出行列式的值，其绝对值就是这个图中生成树的个数。
-
度数矩阵 D[G]：当$ i≠j$ 时，(D[i][j]=0)，当$ i=j$ 时，(D[i][i] = degree(v_i))
-
邻接矩阵 A[G]：当 (v_i)、(v_j) 有边连接时，(A[i][j]=1)，当 (v_i)、(v_j) 无边连接时，(A[i][j]=0)
-
基尔霍夫矩阵(Kirchhoff) K[G]：也称拉普拉斯算子，其定义为(K[G]=D[G]-A[G])，即：(K[i][j]=D[i][j]-A[i][j])
取模
- 图中节点的下标从0开始计数！
- 不存在自环，允许存在重边
- 求行列式参数为n，求生成树计数参数为n-1
typedef long long ll;
ll mod;
const int N = 205;
struct Matrix {
ll mat[N][N];
void init() {
memset(mat,0,sizeof(mat));
}
void addEdge(int u,int v) {
mat[u][v]--;
mat[u][u]++;
}
ll det(int n){
ll res=1;
for(int i=0;i<n;++i){
if(!mat[i][i]){
bool flag=false;
for(int j=i+1;j<n;++j){
if(mat[j][i]){
flag=true;
for(int k=i;k<n;++k) swap(mat[i][k],mat[j][k]);
res=-res;
break;
}
}
if(!flag) return 0;
}
for(int j=i+1;j<n;++j){
while(mat[j][i]){
ll t=mat[i][i]/mat[j][i];
for(int k=i;k<n;++k){
mat[i][k]=(mat[i][k]-t*mat[j][k])%mod;
swap(mat[i][k],mat[j][k]);
}
res=-res;
}
}
res*=mat[i][i];
res%=mod;//模意义下的语句，不是模意义则不加
}
if(res<0) res+=mod;
return res;
}
}ret;
调用(求行列式)：
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%lld", &ret.mat[i][j]);
}
}
printf("%lld
", ret.det(n));
取逆元（mod为质数）
- 图中节点的下标从0开始计数！
- 不存在自环，允许存在重边
- 求行列式参数为n，求生成树计数参数为n-1
typedef long long ll;
const ll mod = 998244353;
const int N = 105;
const int M = 1e4 + 5;
ll inv(ll a) {
if(a == 1)return 1;
return inv(mod%a)*(mod-mod/a)%mod;
}
struct Matrix {
ll mat[N][N];
void init() {
memset(mat,0,sizeof(mat));
}
void addEdge(int u,int v) {
mat[u][v]--;
mat[u][u]++;
}
ll det(int n) { //求行列式的值模上MOD，需要使用逆元
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
mat[i][j] = (mat[i][j]%mod+mod)%mod;
ll res = 1;
for(int i = 0; i < n; i++) {
for(int j = i; j < n; j++)
if(mat[j][i]!=0) {
for(int k = i; k < n; k++)
swap(mat[i][k],mat[j][k]);
if(i != j)
res = (-res+mod)%mod;
break;
}
if(mat[i][i] == 0) {
res = 0;//不存在(也就是行列式值为0)
break;
}
for(int j = i+1; j < n; j++) {
//int mut = (mat[j][i]*INV[mat[i][i]])%MOD;//打表逆元
ll mut = (mat[j][i]*inv(mat[i][i]))%mod;
for(int k = i; k < n; k++)
mat[j][k] = (mat[j][k]-(mat[i][k]*mut)%mod+mod)%mod;
}
res = (res * mat[i][i])%mod;
}
return res;
}
}ret;
调用：
ret.init();
for (int i = 1; i <= m; i++) {
scanf("%d%d%lld", &e[i].u, &e[i].v, &e[i].w);
ret.addEdge(--e[i].u, --e[i].v);
ret.addEdge(e[i].v, e[i].u);
}
ll tot = ret.det(n-1);
if(tot == -1) {
puts("0");
continue;
}
不取模
- 图中节点的下标从1开始计数！
- 不存在自环，允许存在重边
- 求行列式参数为n，求生成树计数参数为n-1
typedef long long ll;
const int N = 55;
struct Matrix {
ll mat[N][N];
void init() {
memset(mat, 0, sizeof mat);
}
ll gauss(int n) {
ll res = 1;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
while (mat[j][i]) {
ll t = mat[i][i] / mat[j][i];
for (int k = i; k <= n; k++)
mat[i][k] = (mat[i][k] - t * mat[j][k]);
swap(mat[i], mat[j]);
res = -res;
}
}
if(mat[i][i] == 0) return 0;
res = res * mat[i][i];
}
if(res < 0) res = -res;
return res;
}
void add(int u, int v) {
mat[u][u]++;
mat[v][v]++;
mat[u][v]--;
mat[v][u]--;
}
}ret;
调用：
ret.init();
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
ret.add(u, v);
}
printf("%lld
", ret.gauss(n-1));
最小生成树计数（Kruskal+Matrix-Tree）
用kruscal计算最小生成树时，每次取连接了两个不同联通块的最小的边。也就是先处理(d_1)条(c_1)长度的边，再处理(d_2)条(c_2)长度的边。长度相同的边无论怎么选，最大联通情况都是固定的。 分别对(c_i)长度的边产生的几个联通块计算生成树数量再乘起来，然后把这些联通块缩点，再计算(c_{i+1})长度的边。
并查集(fa[i])是当前长度之前，节点所属的联通块，(ka[i])是当前长度的边连接后它在的联通块。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int N=101;
const int M=1001;
ll n,m,p,ans;
vector<int>gra[N];
struct edge{
int u,v,w;
}e[M];
int cmp(edge a,edge b){
return a.w<b.w;
}
ll mat[N][N],g[N][N];
ll fa[N],ka[N],vis[N];
ll det(ll c[][N],ll n){
ll i,j,k,t,ret=1;
for(i=0;i<n;i++)
for(j=0;j<n;j++) c[i][j]%=p;
for(i=0; i<n; i++){
for(j=i+1; j<n; j++)
while(c[j][i]){
t=c[i][i]/c[j][i];
for(k=i; k<n; k++)
c[i][k]=(c[i][k]-c[j][k]*t)%p;
swap(c[i],c[j]);
ret=-ret;
}
if(c[i][i]==0)
return 0L;
ret=ret*c[i][i]%p;
}
return (ret+p)%p;
}
ll find(ll a,ll f[]){
return f[a]==a?a:find(f[a],f);
}
void matrix_tree(){//对当前长度的边连接的每个联通块计算生成树个数
for(int i=0;i<n;i++)if(vis[i]){//当前长度的边连接了i节点
gra[find(i,ka)].push_back(i);//将i节点压入所属的联通块
vis[i]=0;//一边清空vis数组
}
for(int i=0;i<n;i++)
if(gra[i].size()>1){//联通块的点数为1时生成树数量是1
memset(mat,0,sizeof mat);//清空矩阵
int len=gra[i].size();
for(int j=0;j<len;j++)
for(int k=j+1;k<len;k++){//构造这个联通块的矩阵（有重边）
int u=gra[i][j],v=gra[i][k];
if(g[u][v]){
mat[k][j]=(mat[j][k]-=g[u][v]);
mat[k][k]+=g[u][v];mat[j][j]+=g[u][v];
}
}
ans=ans*det(mat,gra[i].size()-1)%p;
for(int j=0;j<len;j++)fa[gra[i][j]]=i;//缩点
}
for(int i=0;i<n;i++)
{
gra[i].clear();
ka[i]=fa[i]=find(i,fa);
}
}
int main(){
while(scanf("%lld%lld%lld",&n,&m,&p),n){
for(int i=0;i<m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
u--;v--;
e[i]=(edge){u,v,w};
}
sort(e,e+m,cmp);
memset(g,0,sizeof g);
ans=1;
for(ll i=0;i<n;i++)ka[i]=fa[i]=i;
for(ll i=0;i<=m;i++){//边从小到大加入
if(i&&e[i].w!=e[i-1].w||i==m)//处理完长度为e[i-1].w的所有边
matrix_tree();//计算生成树
ll u=find(e[i].u,fa),v=find(e[i].v,fa);//连的两个缩点后的点
if(u!=v)//如果不是一个
{
vis[v]=vis[u]=1;
ka[find(u,ka)]=find(v,ka);//两个分量在一个联通块里。
g[u][v]++,g[v][u]++;//邻接矩阵
}
}
int flag=1;
for(int i=1;i<n;i++)if(fa[i]!=fa[i-1])flag=0;
printf("%lld
",flag?ans%p:0);//注意p可能为1，这样m=0时如果ans不%p就会输出1
}
}