AT_jsc2021_g Spanning Tree 题解

感觉自己稍微有一点唐了。

思路

我们首先可以把一定要连的边连起来。

这样就变成了一个无向图生成树计数问题。

如何求解。

使用矩阵树定理！

我们可以求出基尔霍夫矩阵，然后跑一遍行列式就可以了。

时间复杂度：\(O(n^3)\)。

Code

#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;

int n, m;
int fa[310];
int id[310];
int a[310][310];
int f[310][310];

inline int gf(int x) { return (x == fa[x] ? x : fa[x] = gf(fa[x])); }
inline long long power(long long x, long long y) {
  long long res = 1;
  while (y) { if (y & 1) res = res * x % mod; x = x * x % mod, y /= 2; }
  return res;
}

int main() {
  cin >> n;
  iota(fa + 1, fa + n + 1, 1);
  for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> a[i][j];
  for (int i = 1; i <= n; i++) for (int j = i; j <= n; j++)
    if (a[i][j] == 1) {
      if (gf(i) == gf(j)) cout << 0 << "\n", exit(0);
      fa[gf(i)] = gf(j);
    }
  for (int i = 1; i <= n; i++) if (fa[i] == i) id[i] = ++m;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      if (a[i][j] == -1) {
        f[id[gf(i)]][id[gf(j)]]--;
        f[id[gf(i)]][id[gf(i)]]++;
      }
  int ans = 1;
  for (int i = 1; i < m; i++) {
    int p = i;
    for (int j = i; j < m; j++) if (f[j][i]) p = i;
    if (p != i) ans = ans * -1, swap(f[p], f[i]);
    int q = power(f[i][i], mod - 2);
    for (int j = i + 1; j < m; j++) {
      int z = 1ll * f[j][i] * q % mod;
      for (int k = 1; k <= m; k++) {
        f[j][k] = (f[j][k] - 1ll * z * f[i][k]) % mod;
      }
    }
  }
  for (int i = 1; i < m; i++) ans = 1ll * ans * f[i][i] % mod;
  cout << (ans + mod) % mod << "\n";
}