spoj 104 Highways（Matrix-tree定理）

生成树计数，matrix-tree定理的应用。

Matrix-tree定理：

D为无向图G的度数矩阵（D[i][i]是i的度数，其他的为0），A为G的邻接矩阵（若u,v之间存在边，A[u][v]=A[v][u]=1）,C=D-A。

对于一个无向图G，它的生成树个数等于其Kirchhoff矩阵任何一个n-1阶主子式的行列式的绝对值。所谓n-1阶主子式，就是对于任意一个r，将C的第r行和第r列同表示时删去后的新矩阵，表示为Cr。

求行列式的值：

把矩阵用高斯消元消成上三角矩阵，对角线的积就是行列式的值。

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<iostream>

 #include<cmath>

 using namespace std;

 const double eps = 1e-;

 double c[][];

 int T,n,m;

 double Gauss() {

     for (int k=; k<=n; ++k) {

         int r = k;

         for (int i=k+; i<=n; ++i)

             if (fabs(c[i][k]) > fabs(c[r][k])) r = i;

         if (r!=k) for (int j=; j<=n; ++j) swap(c[k][j],c[r][j]);

         for (int i=k+; i<=n; ++i)

             if (fabs(c[i][k]) > eps) {

                 double t = c[i][k] / c[k][k];

                 for (int j=k; j<=n; ++j) c[i][j] -= t*c[k][j];

             }

     }

     double ans = 1.0;

     for (int i=; i<=n; ++i) ans = ans*c[i][i]; //矩阵的对角线乘积

     return (ans > ) ? ans : -ans;//取绝对值

 }

 int main() {

     scanf("%d",&T);

     while (T--) {

         memset(c,,sizeof(c));

         scanf("%d%d",&n,&m);

         for (int u,v,i=; i<=m; ++i) {

             scanf("%d%d",&u,&v);

             c[u][v] = c[v][u] = -;//边

             c[u][u] ++;c[v][v] ++;//度数

         }

         n--; // 去掉最后一行最后一列

         double ans = Gauss(); //高斯消元

         printf("%.0lf\n",ans+eps);

     }

     return ;

 }

巴特西

spoj 104 Highways（Matrix-tree定理）

最新文章

热门文章