首页 > 代码库 > 【生成树计数】专题总结

【生成树计数】专题总结

2024-07-04 13:44:29   224人阅读

在CTSC和APIO上好像经常听到生成树计数这东西

于是就去看了下论文

蒟蒻表示看不懂证n明orz 反正懂用就行了。。

 

生成树计数

生成树计数就是给出一种n个点的无向图G 求这n个点的生成树个数

G的度数矩阵d[i][j] 当i≠j时d[i][j]=0 否则等于i点的度数

G的邻接矩阵a[i][j] a[i][j]=i、j间的边的个数（能有重边）

Kirchhoff矩阵 c[i][j]=d[i][j]-a[i][j]

Kirchhoff矩阵的n-1阶主子式的行列式的值的绝对值即为生成树的个数

n-1阶主子式即为把原矩阵去掉任意第i行和第i列得到的矩阵

 

行列式的值的计算

行列式的算法一般是用高斯消元计算出上三角矩阵 再把主对角线的值累成起来

但是高斯消元可能会导致出现小数

于是我们用一种类似求gcd的方法 辗转消除即可

这里要注意 如果交换矩阵的某两行 行列式的值要*-1 （虽然对生成树计数的计算没影响- -）

 

最小生成树计数代码

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 using namespace std;
  5 const int N=101,M=1001,mo=31011;
  6 struct info{
  7     int x,y,lon;
  8     info(const int a=0,const int b=0,const int c=0):
  9         x(a),y(b),lon(c){}
 10 }sl[M];
 11 struct inli{
 12     int next,data;
 13     inli(const int a=0,const int b=0):
 14         next(a),data(b){}
 15 }line[M*2];
 16 int n,m,nl,num,change[N],save[N],bo[N],link[N][N],son[N],jz[N][N],fat[N],d[N],ans=1;
 17 inline bool cmp(info x,info y){ return x.lon<y.lon; }
 18 void clean(){
 19     memset(jz,0,sizeof(jz));
 20     memset(bo,0,sizeof(bo));
 21     memset(son,0,sizeof(son));
 22     nl=0;
 23 }
 24 int getfat(int t){ return fat[t] ? fat[t]=getfat(fat[t]) : t; }
 25 void search(int t){
 26     bo[t]=2,save[++save[0]]=t;
 27     for (int i=son[t];i;i=line[i].next)
 28     if (bo[line[i].data]==1) search(line[i].data);
 29 }
 30 void swap(int x,int y){
 31     for (int i=1;i<=num;i++){ int t=jz[x][i]; jz[x][i]=jz[y][i],jz[y][i]=t; }
 32 }
 33 void gcd(int x,int y,int t){
 34     while (jz[y][t]){
 35         if (abs(jz[x][t])>abs(jz[y][t])) swap(x,y);
 36         //abs
 37         int xx=jz[y][t]/jz[x][t];
 38         for (int j=t;j<=num;j++) jz[y][j]=(jz[y][j]-jz[x][j]*xx%mo)%mo;
 39         //need %mo
 40     }
 41 }
 42 int getans(){
 43     int res=1;
 44     num=save[0]-1;
 45     for (int i=1;i<=num;i++){
 46         if (!jz[i][i])
 47         for (int j=i+1;j<=num;j++)
 48         if (jz[j][i]){
 49             swap(i,j);
 50             break;
 51         }
 52         for (int j=i+1;j<=num;j++)
 53         if (jz[j][i]) gcd(i,j,i);
 54     }
 55     for (int i=1;i<=num;i++) res=res*jz[i][i]%mo;
 56     return res<0 ? -res : res;
 57 }
 58 void makeans(){
 59     for (int i=1;i<=n;i++)
 60     if (bo[i]==1){
 61         save[0]=0;
 62         search(i);
 63         for (int i=1;i<=save[0];i++)
 64         for (int j=1;j<=save[0];j++) jz[i][j]=0;
 65         change[0]=0;
 66         for (int i=1;i<=save[0];i++) change[save[i]]=++change[0];
 67         for (int j=1;j<=save[0];j++){
 68             int now=save[j];
 69             for (int k=son[now];k;k=line[k].next){
 70                 ++jz[change[now]][change[now]];
 71                 --jz[change[now]][change[line[k].data]];
 72             }
 73         }
 74         ans=ans*getans()%mo;
 75         for (int j=2;j<=save[0];j++) fat[save[j]]=save[1];
 76     }
 77 }
 78 void work(){
 79     sort(sl+1,sl+m+1,cmp);
 80     for (int i=1;i<=m;){
 81         int save=sl[i].lon;
 82         clean();
 83         for (;i<=m && sl[i].lon==save;++i){
 84             int x=getfat(sl[i].x),y=getfat(sl[i].y);
 85             if (x==y) continue;
 86             bo[x]=bo[y]=1;
 87             line[++nl]=inli(son[x],y),son[x]=nl;
 88             line[++nl]=inli(son[y],x),son[y]=nl;
 89         }
 90         makeans();
 91     }
 92 }
 93 int main(){
 94     freopen("bz1016.in","r",stdin);
 95     freopen("bz1016.out","w",stdout);
 96     scanf("%d%d",&n,&m);
 97     for (int x,y,z,i=1;i<=m;i++){
 98         scanf("%d%d%d",&x,&y,&z);
 99         sl[i]=info(x,y,z);
100     }
101     work();
102     memset(bo,0,sizeof(bo));
103     int add=0;
104     for (int i=1;i<=n;i++)
105     if (!bo[getfat(i)]) add+=bo[getfat(i)]=1;
106     if (add>1) puts("0");
107     else printf("%d",ans);
108     fclose(stdin);
109     fclose(stdout);
110 }
View Code

 


联系
我们