SPOJ 104 Highways 最小生成树计数

#pragma comment(linker, "/STACK:1024000000,1024000000") #include<bits/stdc++.h> template <class T> inline bool rd(T &ret) { char c; int sgn; if(c=getchar(),c==EOF) return 0; while(c!='-'&&(c<'0'||c>'9')) c=getchar(); sgn=(c=='-')?⑴:1; ret=(c=='-')?0:(c-'0'); while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn; return 1; } template <class T> inline void pt(T x) { if (x <0) { putchar('-'); x = -x; } if(x>9) pt(x/10); putchar(x%10+'0'); } using namespace std; typedef long long ll; const int N = 15; ll a[N][N],g[N][N]; void add(int u, int v){ u--; v--; g[u][v] = g[v][u] = 1; } ll DET(int n){ //点标从[0, n) for(int i=0, u;i<n;i++) { u=0; for(int j=0;j<n;j++) if(g[i][j]) u++,a[i][j]=⑴; a[i][i]=u; } ll temp=1,t; for(int i=1;i<n;i++) { for(int j=i+1;j<n;j++) while(a[j][i]) { t=a[i][i]/a[j][i]; for(int k=i;k<n;k++) a[i][k]-=a[j][k]*t; for(int k=i;k<n;k++) { t=a[i][k]; a[i][k]=a[j][k]; a[j][k]=t; } temp=-temp; } temp=temp*a[i][i]; } if(temp<0) temp=-temp; return temp; } void init(){ memset(a,0,sizeof(a)); memset(g,0,sizeof(g)); } int n, m; int main(){ int T, u, v; rd(T); while(T--){ rd(n); rd(m); init(); while(m--){ rd(u); rd(v); add(u,v); } pt(DET(n)); putchar(' '); } return 0; }