行列式求法和矩阵树定理

1.矩阵树定理
无向图,有n个点,如果说i-j之间有连边,那么矩阵g[i][j]=g[j][i]=-1(i-j之间的边的数量),否则值为0
矩阵上对角线上的值为该点的度数,g[i][i]=d[i];
生成树个数:任选i,去掉i行i列之后的行列式的值
生成树的权值=边权的乘积,所有生成树的权值之和?
i-j之间右边,g[i][j]=-w[i][j]之和
g[i][i]=所有w[i][j]之和

时间复杂度:n^3logW

int g[N][N];int calc(int n){int ans=1;for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) g[i][j]%=mod;for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){int x=i,y=j;while(g[x][i]){int t=g[y][i]/g[x][i];for(int k=i;k<=n;k++){g[y][k]=(g[y][k]-t*g[x][k])%mod;}swap(x,y);}if(x==i){for(int k=i;k<=n;k++) swap(g[i][k],g[j][k]);ans=-ans;}if(g[i][i]==0){return 0;}ans=ans*g[i][i]%mod;}if(ans<0)ans+=mod;return ans;}void slove(){int n,m;cin>>n>>m;for(int i=1;i<=m;i++){int u,v;cin>>u>>v;g[u][v]--,g[v][u]--;g[u][u]++,g[v][v]++;}cout<<calc(n-1)<<endl;//删掉第n行,第n列 
}