【BZOJ】4596: [Shoi2016]黑暗前的幻想乡

【题意】给定n个点的无向完全图，有n-1个公司各自分管一部分路，要求所有公司都有修路的生成树数。n<=17。

【算法】容斥原理+生成树计数（矩阵树定理）

【题解】每个生成树方案是一个公司有无修路的01排列，定义集合x为公司x有修路的方案集合，则题目要求集合交。

对于若干集合的集合并补集，即x个公司不修路的方案数，就是除去这x个公司的边的生成树数。

ans=Σ(-1)^k g(k)，0<=k<=n-1。g(k)表示枚举k个公司不修的生成树数。

复杂度O(2^(n-1)*n^3)。

注意：

1.答案变成非负数。

2.公司边集最大N*N。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=,MOD=1e9+;

int a[maxn][maxn],b[maxn][maxn*maxn][],sz[maxn],n,ans;//

bool c[maxn];

void gcd(int a,int b,int &x,int &y){

    if(!b){x=;y=;}

    else{gcd(b,a%b,y,x);y-=x*(a/b);}

}

int inv(int a){int x,y;gcd(a,MOD,x,y);return (x%MOD+MOD)%MOD;}

int det(int n){

    for(int i=;i<=n;i++)for(int j=;j<=n;j++)a[i][j]=(a[i][j]+MOD)%MOD;

    bool y=;

    for(int i=;i<=n;i++){

        int r=i;

        for(int j=i+;j<=n;j++)if(a[j][i]>a[r][i])r=j;

        if(r!=i){y^=;for(int j=i;j<=n;j++)swap(a[r][j],a[i][j]);}

        int v=inv(a[i][i]);

        for(int j=i+;j<=n;j++){

            for(int k=n;k>=i;k--){

                a[j][k]=(a[j][k]-1ll*a[j][i]*v%MOD*a[i][k]%MOD+MOD)%MOD;

            }

        }

    }

    int as=y?MOD-:;

    for(int i=;i<=n;i++)as=1ll*as*a[i][i]%MOD;

    return as;

}

void insert(int u,int v){a[u][v]--;a[v][u]--;a[u][u]++;a[v][v]++;}

int solve(){

    memset(a,,sizeof(a));

    for(int i=;i<n;i++)if(!c[i]){//

        for(int j=;j<=sz[i];j++)insert(b[i][j][],b[i][j][]);

    }

    return det(n-);

}

void dfs(int x,int y){

    if(x==n){

        ans=(ans+y*solve())%MOD;

    }

    else{

        c[x]=;

        dfs(x+,y);

        c[x]=;

        dfs(x+,-y);

    }

}

int main(){

    scanf("%d",&n);

    for(int i=;i<n;i++){

        scanf("%d",&sz[i]);

        for(int j=;j<=sz[i];j++)scanf("%d%d",&b[i][j][],&b[i][j][]);

    }

    ans=;

    dfs(,);

    printf("%d",(ans+MOD)%MOD);//

    return ;

}

巴特西

【BZOJ】4596: [Shoi2016]黑暗前的幻想乡

最新文章

热门文章