生成树计数

就是对于一个图，求有多少个生成树。

基尔霍夫矩阵树定理：构建一个邻接矩阵，对角线上的点值等于点 i 的度数，如果 i 和 j 有边相连对应矩阵点值为 -1

生成树个数：任意的n-1阶行列式的值。

题目大意：现有n个点，m条边，k为根节点，每条边代表边的两点有矛盾，不能相连，问存在多少生成树。

先处理出补图，跑一遍生成树计数即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
const int N=1e2+50;
int A[N][N],B[N][N];
ll determinant(int n){
    ll res=1;
    for(int i=1;i<=n;i++){
        if(!B[i][i]){
            bool flag=false;
            for(int j=i+1;j<=n;j++){
                if(B[j][i]){
                    flag = true;
                    for(int k=i;k<=n;k++){
                        swap(B[i][k],B[j][k]);
                    }
                    res=-res;
                    break;
                }
            }
            if(! flag)
            return 0;
        }

        for(int j=i+1;j<=n;j ++){
            while(B[j][i]){
                ll t=B[i][i]/B[j][i];
                for(int k=i;k<=n;k ++){
                    B[i][k]=B[i][k]-t*B[j][k];
                    swap(B[i][k],B[j][k]);
                }
                res=-res;
            }
        }
        res*= B[i][i];
    }
    return res;
}
int main(){
    int n,m,k;
    while(~scanf("%d %d %d",&n,&m,&k)){
        memset(A,0,sizeof A);
        memset(B,0,sizeof B);
        for(int i=1,u,v;i<=m;i++){
            scanf("%d %d",&u,&v);
            A[u][v]=A[v][u]=1;
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i!=j&&A[i][j]==0){
                    B[i][i]++;
                    B[i][j]=-1;
                }
            }
        }
        n=n-1;
        ll ans=determinant(n);
        printf("%lldn",ans);
    }
    // system("pause");
    return 0;
}

View Code

原文链接: https://www.cnblogs.com/littlerita/p/12845904.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/347042

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

生成树计数

相关推荐