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

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

A为一个方阵。

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

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

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

NOI2007《生成树计数》中有涉及到Kirchhoff矩阵。详细证明戳进来 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
double a;
#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;
} 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 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. Emma 说:
2023年1月18日 15:56

There are several algorithms for computing the determinant of a matrix, including:Gaussian elimination: This method involves performing row operations on the matrix until it is in row echelon form, at which point the determinant is simply the product of the diagonal elements.LU decomposition: This method involves decomposing the matrix into a lower triangular cannabidiol oil matrix and an upper triangular matrix, and the determinant is the product of the diagonal elements of the upper triangular matrix, Cholesky decomposition, QR decomposition, Adjugate Matrix etc. Which algorithm you choose will depend on the specific characteristics of the matrix you are working with, as well as the resources (computational time and memory) available to you. (输入验证码)
or Ctrl+Enter