Organising the Organisation
生成树计数
要用到Matric-Tree定理。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 const int maxn = 52; 5 const long double eps = 1e-8; 6 long double a[maxn][maxn]; 7 int vis[maxn][maxn]; 8 int dcmp(long double x){ 9 if(fabs(x) < eps) return 0; 10 return x < 0 ? -1 : 1; 11 } 12 long double solve(long double a[][maxn], int n){ 13 long double ans = 1; 14 int cnt = 0; 15 for(int i = 0; i < n; i++){ 16 if(dcmp(a[i][i]) == 0){ 17 int j; 18 for(j = i + 1; j < n; j++){ 19 if(!dcmp(a[j][i])) break; 20 } 21 if(j == n){ 22 return 0; 23 } 24 for(int k = i; k < n; k++){ 25 swap(a[i][k], a[j][k]); 26 } 27 cnt++; 28 } 29 ans *= a[i][i]; 30 for(int j = i + 1; j < n; j++){ 31 long double ta = a[j][i] / a[i][i]; 32 for(int k = i; k < n; k++){ 33 a[j][k] -= ta * a[i][k]; 34 } 35 } 36 } 37 if(cnt & 1) ans = -ans; 38 return ans; 39 } 40 41 int main(){ 42 int n, m, k; 43 while(scanf("%d %d %d", &n, &m, &k) != EOF){ 44 memset(vis, 0, sizeof(vis)); 45 memset(a, 0, sizeof(a)); 46 for(int i = 0; i < m; i++){ 47 int u, v; 48 scanf("%d %d", &u, &v); 49 u--; 50 v--; 51 vis[u][v] = vis[v][u] = 1; 52 } 53 for(int i = 0; i < n; i++){ 54 for(int j = 0; j < n; j++){ 55 if(!vis[i][j] && i != j){ 56 a[i][i]++; 57 a[i][j] = -1; 58 } 59 } 60 } 61 printf("%.0f ", (double)solve(a, n-1)); 62 } 63 }