高速公路（SPOJ104 Highways）
一个有n座城市的组成国家，城市1至n编号，其中一些城市之间可以修建高速公路。现在，需要有选择的修建一些高速公路，从而组成一个交通网络。你的任务是计算有多少种方案，使得任意两座城市之间恰好只有一条路径？
数据规模：1≤n≤12。
生成树计数
算法步骤：
1、 构建拉普拉斯矩阵
Matrix[i][j] =
degree(i) , i==j
-1，i-j有边
0，其他情况
2、 去掉第r行，第r列（r任意）
3、 计算矩阵的行列式
#include <map>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 105;
const int maxm = 100005;
const int INF = 1e9;
int degree[maxn];
ll g[maxn][maxn];
int n, m;
ll det(ll a[][maxn], int n)
{
ll ret = 1;
for(int i=1; i<n; ++i){
for(int j=i+1; j<n; ++j){
while(a[j][i]){
ll t = a[i][i]/a[j][i];
for(int k=i; k<n; ++k){
a[i][k] = (a[i][k]-a[j][k]*t);
}
for(int k=i; k<n; ++k){
swap(a[i][k], a[j][k]);
}
ret = -ret;
}
}
if(a[i][i]==0){
return 0;
}
ret = ret*a[i][i];
}
if(ret<0){
ret = -ret;
}
return ret;
}
void solve()
{
int u, v;
memset(degree, 0, sizeof degree );
memset(g, 0, sizeof g );
scanf("%d%d", &n, &m);
while(m--){
scanf("%d%d", &u, &v);
u--,v--;
g[u][v] = g[v][u] = -1;
degree[u]++;
degree[v]++;
}
for(int i=0; i<n; ++i){
g[i][i] = degree[i];
}
printf("%lld\n", det(g, n));
}
int main()
{
int t;
scanf("%d", &t);
while(t--){
solve();
}
return 0;
}