[JSC2021G] Spanning Tree 题解

FFTotoro · 2024-01-27 19:40:19 · 题解

复习了矩阵树定理，再来试试水。

考虑如何将原问题转换为生成树计数：首先 A_{i,j}=1 的边连接的两个点可以缩成一个点（可以用并查集维护；注意判连通块内的连边，这样是无解的）；然后对于 A_{i,j}=-1 的边（在缩点之后），连接的两个点（实际上是原来的连通块）之间的边有选 / 不选两种选择，于是构造出基尔霍夫矩阵，就是板题了。

可以借助 AtCoder Library 中的 dsu 和 modint 实现。

放代码：

#include<bits/stdc++.h>
#include<atcoder/all>
#define int long long
using namespace std;
using namespace atcoder;
using mint=modint1000000007;
mint det(vector<vector<mint> > &a){
  mint s=1,f=1;
  for(int i=0;i<a.size()-1;i++)
    for(int j=i+1;j<a.size()-1;j++){
      while(a[i][i].val()){
        mint d=a[j][i]/a[i][i];
        for(int k=i;k<a.size()-1;k++)
          a[j][k]-=a[i][k]*d;
        swap(a[i],a[j]),f=-f;
      }
      swap(a[i],a[j]),f=-f;
    }
  for(int i=0;i<a.size()-1;i++)
    s*=a[i][i];
  return s*f;
} // 求行列式
main(){
  ios::sync_with_stdio(false);
  int n,c=0; cin>>n;
  vector a(n,vector<int>(n));
  for(auto &i:a)for(auto &j:i)cin>>j;
  dsu d(n);
  for(int i=0;i<n;i++)
    for(int j=i+1;j<n;j++)
      if(a[i][j]>0){
        if(d.same(i,j))cout<<"0\n",exit(0);
        else d.merge(i,j);
      } // 并查集维护连通块
  vector<int> m(n);
  for(int i=0;i<n;i++)
    if(i==d.leader(i))m[i]=c++;
  vector f(c,vector<mint>(c));
  for(int i=0;i<n;i++)
    for(int j=i+1;j<n;j++)
      if(a[i][j]<0&&!d.same(i,j)){
        int x=m[d.leader(i)],y=m[d.leader(j)];
        f[x][x]++,f[y][y]++,f[x][y]--,f[y][x]--;
      } // 构造基尔霍夫矩阵
  cout<<det(f).val()<<endl;
  return 0;
}