行列式求法和矩阵树定理

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列 
}