生成树的计数及其应用

首先推荐一篇论文：周冬2007年集训队论文：《生成树的计数及其应用》 

然后写一写我的总结和相关题目吧：

相关题目：

• SPOJ104 Highways(HIGH)：题意就是给你n(1<=n<=12)个点，然后告诉你有些点之间可以加边。然后问有多少种加边方案，使得任意俩点之间有且只有一条路径，裸的生成树的计数。由于n很小。dp也行。 也可以直接套用上面的做法。利用Kirchhoff矩阵来求。代码君：

  #include <cstdio>
  #include <cstring>
  #include <algorithm>
  #include <iostream>
  using namespace std;
  
  const int maxn = 15;
  const double eps = 1e-8;
  int test, n, m, x, y;
  double mat[maxn][maxn];
  int num[maxn];
  
  inline bool zero(double x) {
      return x > -eps && x < eps;
  }
  
  double doit() {
      double tmp = 0, result = 1;
      for (int i = 0; i < maxn; i++)
          num[i] = i;
      for (int i = 1; i < n; i++) {
          if (zero(mat[num[i]][i])) {
              for (int j = i + 1; j < n; j++) {
                  if (!zero(mat[num[j]][i])) {
                     swap(num[i], num[j]); result *= -1; break;
                  }
              }
          }
          result *= mat[num[i]][i];
          for (int j = i + 1; j < n; j++) {
              if (!zero(mat[num[j]][i])) {
                  tmp = mat[num[j]][i] / mat[num[i]][i];
                  for (int k = i; k < n; k++)
                      mat[num[j]][k] -= mat[num[i]][k] * tmp;
              }
          }
      }
      return result;
  }
  
  int main() {
      scanf("%d", &test);
      for (int cas = 1; cas <= test; cas++) {
          scanf("%d %d", &n, &m);
          memset(mat, 0, sizeof(mat));
          for (int i = 1; i <= m; i++) {
              scanf("%d %d", &x, &y);
              mat[x][x]++; mat[y][y]++;
              mat[x][y]--; mat[y][x]--;
          }
          printf("%.0f\n", doit());
      }
      return 0;
  }