大的道理和理论我就不说了，有什么理论上的疑惑我推荐下这个地址：
https://blog.csdn.net/u013010295/article/details/47451451
一：无向图中的生成树计数；
这种情况下我们要看看是否存在重边的情况，如果没有的话就可以用Matrix-Tree定理和高斯消元直接来解；
map代表我们的图中的边是否存在，
而dre便是我们计算所需要的数组，他的对角线元素的值分别代表着某个点她的度的大小（包括入度和出度，其实就是加起来），非对角线元素就是代表着某个边是否存在，存在的话标为-1，不存在的话标为0；
首先是需要取余的；
#include<cstdio>
#include<iostream>
using namespace std;
#define ll long long int
char map[15][15];
ll dre[105][105];
int n, m;
ll mod = 1e9;
long long solve(int n)
{
ll ans = 1;
for (int s = 1; s < n; s++)
{
for (int w = s + 1; w < n; w++)
while (dre[w][s])
{
ll t = dre[s][s] / dre[w][s];
for (int k = s; k < n; k++)
{
dre[s][k] = (dre[s][k] - dre[w][k] * t%mod + mod) % mod;
swap(dre[s][k], dre[w][k]);
}
ans = -ans;
}
if (dre[s][s] == 0)
return 0;
ans = (ans*dre[s][s]) % mod;
}
return (ans + mod) % mod;
}
其次是不需要取余的
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
#define ll long long int
long long dre[55][55];
bool map[55][55];
int n, m, k;
const long long eps = 1e-10;
long long solve(int n)
{
ll ret = 1;
for (int i = 1; i<=n; i++)
{
for (int j = i + 1; j<=n; j++)
while (dre[j][i])
{
ll t = dre[i][i] / dre[j][i];
for (int k = i; k<=n; k++)
dre[i][k] = (dre[i][k] - dre[j][k] * t);
for (int k = i; k<=n; k++)
swap(dre[i][k], dre[j][k]);
ret = -ret;
}
if (dre[i][i] == 0)
return 0;
ret = ret*dre[i][i];
}
if (ret<0)
ret = -ret;
return ret;
}
int main()
{
while (~scanf("%d%d%d", &n, &m, &k)) {
memset(map, 0, sizeof(map));
memset(dre, 0, sizeof(dre));
while (m--)
{
int a, b;
scanf("%d%d", &a, &b);
map[a][b] = map[b][a] = 1;
}
for (int s = 1; s <= n; s++) {
for (int w = s + 1; w <= n; w++) {
if (!map[s][w])
dre[s][s]++, dre[s][w] = -1, dre[w][w]++, dre[w][s] = -1;
}
}
printf("%lld\n", solve(n - 1));
}
} 精度需求高的：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
#define ll long long int
long double dre[55][55];
bool map[55][55];
int n, m, k;
const long double eps = 1e-10;
int sgn(long double x)
{
if (fabs(x)<eps) return 1; return 0;
}
long double solve(int n)
{
for (int s = 1; s <= n; s++) {
int maxn = s;
for (int w = s + 1; w <= n; w++) {
if (fabs(dre[w][s]) > fabs(dre[maxn][s])) {
maxn = s;
}
}
if (sgn(dre[maxn][s]))return 0;
if (maxn != s) {
for (int w = s; w <= n; w++) {
swap(dre[s][w], dre[maxn][w]);
}
}
for (int w = s + 1; w <= n; w++) {
long double temp = dre[w][s] / dre[s][s];
for (int e = s; e <= n; e++) {
dre[w][e] -= temp*dre[s][e];
}
}
}
long double ans = 1;
for (int s = 1; s <= n; s++) {
ans *= dre[s][s];
}
ans = fabs(ans);
return ans;
}
int main()
{
while (~scanf("%d%d%d", &n, &m, &k)) {
memset(map, 0, sizeof(map));
memset(dre, 0, sizeof(dre));
while (m--)
{
int a, b;
scanf("%d%d", &a, &b);
map[a][b] = map[b][a] = 1;
}
for (int s = 1; s <= n; s++) {
for (int w = s + 1; w <= n; w++) {
if (!map[s][w])
dre[s][s]++, dre[s][w] = -1, dre[w][w]++, dre[w][s] = -1;
}
}
printf("%.0Lf\n", solve(n - 1));
}
} 而当存在重边（重边算多次）的时候，就需要用kruskal算法（此代码来自https://www.cnblogs.com/CtrlCV/p/5668752.html）
#include <bits/stdc++.h>
using namespace std;
struct edge
{
int u, v, w, x;
inline bool operator< (const edge &rhs) const
{
return x < rhs.x;
}
}e[100005];
struct count
{
int l, r, use;
}g[100005];
int n, m, fa[50005], siz[50005];
int getfa(int x)
{
return fa[x] == x ? x : getfa(fa[x]);
}
void link(int u, int v)
{
if(siz[u] > siz[v]) fa[v] = u, siz[u] += siz[v];
else fa[u] = v, siz[v] += siz[u];
}
bool Kruskal()
{
int cnt = 0, u, v;
for(int i = 1; i <= m; ++i)
{
u = getfa(e[i].u), v = getfa(e[i].v);
if(u != v)
{
link(u, v);
++g[e[i].w].use;
if(++cnt == n - 1) return true;
}
}
return false;
}
int DFS(int w, int i, int k)
{
if(k == g[w].use) return 1;
if(i > g[w].r) return 0;
int ans = 0, u = getfa(e[i].u), v = getfa(e[i].v);
if(u != v)
{
link(u, v);
ans = DFS(w, i + 1, k + 1);
fa[u] = u, fa[v] = v;
}
return ans + DFS(w, i + 1, k);
}
int main()
{
int u, v, w, ans;
cin >> n >> m;
for(int i = 1; i <= n; ++i)
fa[i] = i, siz[i] = 1;
for(int i = 1; i <= m; ++i)
{
cin >> u >> v >> w;
e[i] = (edge){u, v, 0, w};
}
sort(e + 1, e + m + 1);
w = 0;
for(int i = 1; i <= m; ++i)
if(e[i].x == e[i - 1].x) e[i].w = w;
else
{
g[w].r = i - 1;
e[i].w = ++w;
g[w].l = i;
}
g[w].r = m;
ans = Kruskal();
for(int i = 1; i <= n; ++i)
fa[i] = i, siz[i] = 1;
for(int i = 1; i <= w; ++i)
{
// ans = ans * DFS(i, g[i].l, 0) % 1000003; 看题意是否需要余
for(int j = g[i].l; j <= g[i].r; ++j)
{
u = getfa(e[j].u), v = getfa(e[j].v);
if(u != v) link(u, v);
}
}
cout << ans << endl;
return 0;
}
二：有向图的生成树计数；
外向树：所有边的方向都是从根指向叶子
内向树：所有边的方向都是从叶子指向根
无论是求外向树还是内向树，都可以用矩阵树定理来做，不过不同的是，在算外向树的时候，所计算的矩阵中的对角线元素代表的是点的出度，而且除对角线元素外，代表的是又向的路是否存在（存在就设为-1）；内向图也一样，只不过对角线元素代表的是点的出度罢了
京公网安备 11010502036488号