生成树的计数及其应用

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

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

相关题目：

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

  1 #include <cstdio>
   2 #include <cstring>
   3 #include <algorithm>
   4 #include <iostream>
   5 using namespace std;
   6 
   7 const int maxn = 15;
   8 const double eps = 1e-8;
   9 int test, n, m, x, y;
  10 double mat[maxn][maxn];
  11 int num[maxn];
  12 
  13 inline bool zero(double x) {
  14     return x > -eps && x < eps;
  15 }
  16 
  17 double doit() {
  18     double tmp = 0, result = 1;
  19     for (int i = 0; i < maxn; i++)
  20         num[i] = i;
  21     for (int i = 1; i < n; i++) {
  22         if (zero(mat[num[i]][i])) {
  23             for (int j = i + 1; j < n; j++) {
  24                 if (!zero(mat[num[j]][i])) {
  25                    swap(num[i], num[j]); result *= -1; break;
  26                 }
  27             }
  28         }
  29         result *= mat[num[i]][i];
  30         for (int j = i + 1; j < n; j++) {
  31             if (!zero(mat[num[j]][i])) {
  32                 tmp = mat[num[j]][i] / mat[num[i]][i];
  33                 for (int k = i; k < n; k++)
  34                     mat[num[j]][k] -= mat[num[i]][k] * tmp;
  35             }
  36         }
  37     }
  38     return result;
  39 }
  40 
  41 int main() {
  42     scanf("%d", &test);
  43     for (int cas = 1; cas <= test; cas++) {
  44         scanf("%d %d", &n, &m);
  45         memset(mat, 0, sizeof(mat));
  46         for (int i = 1; i <= m; i++) {
  47             scanf("%d %d", &x, &y);
  48             mat[x][x]++; mat[y][y]++;
  49             mat[x][y]--; mat[y][x]--;
  50         }
  51         printf("%.0f\n", doit());
  52     }
  53     return 0;
  54 }      

转载于:https://www.cnblogs.com/phonism/archive/2013/04/20/3032627.html