那么，现在就可以进入正题了-------->矩阵树定理(Matrix Tree Theorem)
不知道矩阵行列式等线性代数知识的，请左转：点击打开链接
Part 1 Matrix Tree定理
引入几个概念：
一个图的邻接矩阵G：对于无向图的边(u,v)，G[u][v]++,G[v][u]++
一个图的度数矩阵D：对于无向图的边(u,v)，D[u][u]++,D[v][v]++;
而通过这两个矩阵就可以构造出图G的基尔霍夫矩阵：C=D-G.
Matrix Tree定理：将图G的基尔霍夫矩阵去掉第i行和第i列(i可以取任意值，可以证明所得到的结果相同)，得到(n-1)*(n-1)的矩阵，
对这个矩阵进行行列式的值求解，abs(det(A))即为图G的生成树个数。
求解矩阵行列式的时候，计算常数k时为了避免精度丢失，可以通过计算逆元进行求解(不需要取模时，mod一个大质数即可).
下面给一道MatrixTree定理裸题：SPOJ P104 Highways
Part 2 Matrix Tree定理在有向图上的拓展
Matrix Tree定理的拓展与延伸------有向图的Matrix Tree定理
对于有向图G，不存在生成树的概念，但存在树形图的概念。
树形图：以i点为根节点的树形图有(n-1)条边，从i节点出发可以到达其他所有(n-1)个节点.
定义： 有向图的邻接矩阵G：对于有向图的边(u,v)，G[u][v]++.
有向图的度数矩阵D：对于有向图的边(u,v)，D[v][v]++.
尤其需要注意的是：有向图的度数矩阵指的是一个点的入度，而不是出度。
而有向图的基尔霍夫矩阵的构造方式是一模一样的：C=D-G.
有向图Matrix Tree定理：
将有向图G的基尔霍夫矩阵去掉第i行和第i列，得到(n-1)*(n-1)的矩阵，
对这个矩阵进行行列式的值求解，abs(det(A))就是以i为根的树形图的个数。
最后，来看一道例题：
给一个图G，边带权，定义X树形图为以n号节点为根的树形图的个数，此处树形图定义为有n个点,n-1条边,所有节点都能够到达根节点的图，
求所有X树形图的权值之和，答案mod 1e9+7 。数据范围：n<=50,m<=200
题解:
这道题的树形图定义不太一样，但稍加分析可知，
将边反向，即可转化为以n为根的普通树形图。
接下来，先用上述的定理O(n^3)求出所有符合条件的树形图个数T，
考虑每条边对于答案的贡献：
把第i条边从图G中删除，再求符合条件的树形图个数T’，
这样，T-T’即为这条边所在的树形图个数，
乘以权值后累加即可求得答案。
时间复杂度:O(m*n^3).
这道题通过线性代数技巧优化求行列式的复杂度，
可以做到O(n^3+nm)，这里就不说了.
<其实是博主太弱，不会>
Code:
#include <bits/stdc++.h> #define ll long long #define mod 1000000007ll using namespace std; int u[205],v[205]; ll w[205],a[55][55],c[55][55]; int n,m; inline ll qpow(ll a,ll b) {ll res=1ll,tp=a; while (b) {if (b&1ll) {res*=tp;res%=mod;} tp*=tp;tp%=mod;b>>=1ll; } return res; } inline ll det() {//计算矩阵C的(n-1)阶主子式的行列式的值 int i,j,k; for (i=1;i<=n-1;i++) {for (j=i+1;j<=n-1;j++) {//c[j][i]-p*c[i][i]=0 ll p=(c[j][i]*qpow(c[i][i],mod-2ll))%mod; for (k=i;k<=n-1;k++) {c[j][k]-=p*c[i][k];c[j][k]%=mod; if (c[j][k]<0) {c[j][k]+=mod;} } } } ll ret=1; for (i=1;i<=n-1;i++) {ret*=c[i][i];ret%=mod;} return ret; } int main (){ int i; scanf ("%d%d",&n,&m); for (i=1;i<=m;i++) {scanf ("%d%d%lld",&u[i],&v[i],&w[i]); c[v[i]][u[i]]--;c[u[i]][u[i]]++; } memcpy(a,c,sizeof(c)); ll t1=det(),ans=0; for (i=1;i<=m;i++) {memcpy(c,a,sizeof(a)); c[v[i]][u[i]]++;c[u[i]][u[i]]--; ll t2=(t1-det()+mod)%mod; t2*=w[i];t2%=mod; ans+=t2;ans%=mod; } printf ("%lld\n",ans); return 0; }
