Uva 10766 Organising the Organisation (Matrix_tree 生成树计数)

题目描述：

　　一个由n个部门组成的公司现在需要分层，但是由于员工间的一些小小矛盾，使得他们并不愿意做上下级，问在满足他们要求以后有多少种分层的方案数？

解题思路：

　　生成树计数模板题，建立Kirchhoff矩阵，利用Matrix_tree定理求解。

　　Kirchhoff矩阵：假设G为n*n矩阵，C为G的入度矩阵（i==j时,C[i][j]等于i的入度;i!=j时,C[i][j]等于零），A为G的邻接矩阵，那么就有Kirchhoff矩阵等于C-A。

　　Matrix_tree定理：G的不同生成树的个数等于其所对应的kirchhoff矩阵的n-1阶行列式的绝对值（PS：n-1阶行列式等于Kirchhoff矩阵减去第r行，第r列后所形成的矩阵，其中1<=r<=n）

 #include <cstdio>
 #include <cstring>
 #include <iostream>
 #include <algorithm>
 using namespace std;
 typedef long double LD;
 const int maxn = ;
 const LD sng = 1e-; LD b[maxn][maxn];
 int a[maxn][maxn];
 bool Exp(LD x)
 {
     return ((x>=)?x:-x)<sng;
 }
 LD MTree (int n)
 {
     int sign = , j;
     LD res = ;
     for (int i=; i<n; i++)
     {
         if (Exp(b[i][i]))
         {
             for (j=i+; j<n; j++)
                 if (!Exp(b[j][i]))
                     break;
             if (j == n)
                 return ;
             for (int k=i; k<n; k++)
                 swap (b[i][k], b[j][k]);
             sign ++;
         }
         res *= b[i][i];
         for (j=i+; j<n; j++)
             b[i][j] /= b[i][i];
         for (j=i+; j<n; j++)
             for (int k=i+; k<n; k++)
                 b[j][k] -= b[j][i] * b[i][k];
     }
     if (sign % )
         res = -res;
     return res;
 }
 int main ()
 {
     int n, m, k;
     while (scanf ("%d %d %d", &n, &m, &k) != EOF)
     {
         memset (a, , sizeof(a));
         memset (b, , sizeof(b));
         while (m --)
         {
             int u, v;
             scanf ("%d %d", &u, &v);
             u--, v--;
             a[u][v] = a[v][u] = ;
         }
         for (int i=; i<n; i++)
             for (int j=; j<n; j++)
                 if (!a[i][j] && i != j)
                 {
                     b[i][i] ++;
                     b[i][j] = -;
                 }
         printf ("%.0f\n", (double)MTree (n - ));
     }
     return ;
 }