kuangbin专题八 UVA10766 （生成树计数）Organising the Organisation（请无视这篇文章）

本文主要是介绍kuangbin专题八 UVA10766 （生成树计数）Organising the Organisation（请无视这篇文章），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
给出n,m,k,代表一家公司有n个部门，编号1到n,有m组关系，表示i和j不能直接联通，k代表主管部门，问你有多少种分层方案。另外，这道题的k可以忽略掉，所以他的范围完全是吓唬人的。
题解：
抱歉，这道题我真的无法弄的通俗的说出来，因为这个设计线性代数，我线性代数考试的时候完全是临时抱佛脚的，导致我不太弄懂怎么个弄法，尽管是那个道理，那个意思，但是感觉矩阵没好好懂，还是不明白，所以这篇文章就当是给我自己看的，请大家绕道而行去看别的好的博客。
大佬的解说：

参考一下这个论文：https://wenku.baidu.com/view/0c086741be1e650e52ea990e.html

生成树计数：基尔霍夫矩阵树定理

无向图的基尔霍夫矩阵: 对角线上表示每个点的度数,若ij之间有边则矩阵ij处为-1

无向图的生成树的数目为: 任意一个n-1阶主子式的行列式的绝对值.

思路：

参考周冬的《生成树的计数及其应用》。就是Matrix-Tree定理的应用。

对于一个无向图G，它的生成树个数等于其Kirchhoff矩阵任何一个n-1阶主子式的行列式的绝对值。

所谓n-1阶主子式，就是对于任意一个r，将C的第r行和第r列同时删去后的新矩阵，用Cr表示。

Kirchhoff矩阵：对于无向图G，它的Kirchhoff矩阵C定义为它的度数矩阵D减去它的邻接矩阵A。
题外话:
操，之前参考的那个模板是错误的，只是过了这道题，换个题目就不行，坑了我一上午，去用别的模板就过了，看了假博客是真的难受啊。。操，现在就换过来

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long int
const int MAXN=55;
LL A[MAXN][MAXN];
LL B[MAXN][MAXN];
LL determinant(int n)
{LL res=1;for(int i=1;i<=n;i++){if(!B[i][i]){bool flag=false;for(int j=i+1;j<=n;j++){if(B[j][i]){flag=true;for(int k=i;k<n;k++){swap(B[i][k],B[j][k]);}res=-res;break;}}if(!flag)return 0;}for(int j=i+1;j<=n;j++){while(B[j][i]){LL t=B[i][i]/B[j][i];for(int k=i;k<=n;k++){B[i][k]=B[i][k]-t*B[j][k];swap(B[i][k],B[j][k]);}res=-res;}}res*=B[i][i];}return res;
}
int main()
{int n,m,k;while(~scanf("%d%d%d",&n,&m,&k))//这个k没卵用，完全可以无视 {   memset(A,0,sizeof(A));memset(B,0,sizeof(B));for(int i=1;i<=m;i++){int a,b;scanf("%d%d",&a,&b);A[a][b]=A[b][a]=1;}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i!=j&&!A[i][j]){B[i][i]++;B[i][j]=-1;//减去邻接矩阵 }}}n=n-1;LL ans=determinant(n); printf("%lld\n",ans);}
}