SPOJ-Highways(HIGH)【行列式、Kirchhoff矩阵】

dzy posted @ 2013年8月17日 20:43 in SPOJ with tags SPOJ 行列式 , 2573 阅读

晚上看了会儿线代。

行列式的算法好多。可以根据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;
}
Avatar_small
Digital Ali 说:
2021年9月05日 21:59

Best work you have done, this online website is cool with great facts and looks. I have stopped at this blog after viewing the excellent content. I will be back for more qualitative work. soap2day

Avatar_small
AP SSC Gk Question P 说:
2022年9月11日 18:27

General Knowlorge is most important subject to all Class 10 students studying in English Medium, AP SSC Gk Question Paper Telugu Medium & Urdu Medium of the State Board. So every student who is studying in the state Government & Private Schools can download the AP 10th GK Model Paper 2023 Pdf with answer solutions designed and suggested by subject experts. General Knowlorge is most important subject to all Class 10 students studying in English Medium.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter