晚上看了会儿线代。

行列式的算法好多。可以根据2×2的矩阵行列式计算方法递归。可以用排列、逆序对的神方法算。

效率比较高的应该是基于行变换的一种算法。

令A为一个方阵。

(a). 若A的某一行的倍数加到另一行得矩阵B，则detB=detA.

(b). 若A的两行互换得矩阵B，则detB=-detA.

(c). 若A的某行乘以k倍得到矩阵B，则detB=k*detA.

如果A为三角阵，则detA等于A的主对角线上元素的乘积。

那么我们只需要通过(a)(b)两种变换得到三角阵，计算m=主对角线上元素的乘积。

如果进行了n次(b)操作，那么detA=(-1)^n * m.

可以发现和高斯消元法还是有一些联系的。这种计算行列式的复杂度是O(n^3)。

这道题的题意就是求无向图的生成树个数。

用行列式计算。先构造Kirchhoff矩阵。

NOI2007《生成树计数》中有涉及到Kirchhoff矩阵。详细证明戳进来。

按照这个方法构造。剩下的就是计算行列式了。

可以用double储存。这样(b)操作方便一些。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
double a[20][20];
#define eps 1e-15
inline int dcmp(double p){
        if(fabs(p)<eps)return 0;
        return p>eps?1:-1;
}inline void gauss(int n){
	double tmp=1.0,an=1.0,p;
	for(int i=1,pos;i<=n;i++){
		for(pos=i;(!dcmp(a[pos][i]))&&pos<=n;pos++);
		if(pos>n)	continue;
		for(int j=i;j<=n;j++) swap(a[pos][j],a[i][j]);
		for(int j=i+1;j<=n;j++){
			if(dcmp(a[j][i])){
				if(dcmp(a[i][i])==0||dcmp(a[j][i])==0){	printf("0\n");	return;}
				tmp*=(p=a[i][i]/a[j][i]);
				for(int k=i;k<=n+1;k++) a[j][k]=a[i][k]-a[j][k]*p;
			}
		}
	}for(int i=1;i<=n;i++)	an=an*a[i][i];
	if(n&1)	an*=-1;
	printf("%.0lf\n",fabs(an/tmp));
}int main(){
	int n,m,x,y,tc;	scanf("%d",&tc);
	while(tc--){
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)	for(int j=1;j<=n;j++)	a[i][j]=0;
		for(int i=1;i<=m;i++){
			scanf("%d%d",&x,&y);
			a[x][y]=a[y][x]=-1;
			a[x][x]+=1;	a[y][y]+=1;
		}gauss(n-1);
	}return 0;
}

• 相关文章