首页 > 代码库 > SPOJ - HIGH Highways（矩阵树定理）
SPOJ - HIGH Highways（矩阵树定理）
https://vjudge.net/problem/SPOJ-HIGH
题意：
给n个点m条边，求生成树个数。
思路：
矩阵树裸题。
具体的话可以看一下周冬的论文《生成树的计数及其应用》。
简单说一下，$A[ ][ ]$为邻接矩阵，有边为1（其实也就是边的个数，有重边时要注意），无边为0。$D[ ][ ]$为度数矩阵，$i=j$时为1，否则为0。
$C[ ][ ]$为关联矩阵，$C[ ][ ]=D[ ][ ]-A[ ][ ]$。
最后解任意n-1阶的主子式即可。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath>10 #include<map>11 #include<set>12 using namespace std;13 typedef long long ll;14 typedef pair<int,ll> pll;15 const int INF = 0x3f3f3f3f;16 const int maxn=1000+5;17 18 int n,m;19 double C[maxn][maxn];20 int A[maxn][maxn],D[maxn][maxn];21 22 double Gauss()23 {24 for(int k=1; k<=n; k++) //k表示当前行数，因为行数与列数一样，所以这里k也代表了列数25 {26 int max_r=k;27 for(int i=k+1;i<=n;i++)28 if(fabs(C[i][k]>fabs(C[max_r][k]))) max_r=i;29 if(C[max_r][k]==0) return 0; //有一列为0,行列式的值必为030 if(max_r!=k)31 {32 for(int j=k;j<=n;j++)33 swap(C[k][j],C[max_r][j]);34 }35 for(int i=k+1;i<=n;i++)36 {37 double tmp=C[i][k]/C[k][k];38 for(int j=k;j<=n;j++)39 C[i][j]-=tmp*C[k][j];40 }41 }42 double ans=1;43 for(int i=1;i<=n;i++) ans*=C[i][i]; //化为三角阵后计算主对角线元素乘积44 ans=fabs(ans);45 return ans;46 }47 48 int main()49 {50 //freopen("in.txt","r",stdin);51 int T;52 scanf("%d",&T);53 while(T--)54 {55 memset(A,0,sizeof(A));56 memset(D,0,sizeof(D));57 scanf("%d%d",&n,&m);58 for(int i=0;i<m;i++)59 {60 int u,v;61 scanf("%d%d",&u,&v);62 D[u][u]++; D[v][v]++;63 A[u][v]++; A[v][u]++;64 }65 n--;66 for(int i=1;i<=n;i++)67 for(int j=1;j<=n;j++)68 C[i][j]=D[i][j]-A[i][j];69 printf("%.0lf\n",Gauss());70 }71 return 0;72 }
SPOJ - HIGH Highways（矩阵树定理）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。