题解洛谷 P4336 【[SHOI2016]黑暗前的幻想乡】

生成树计数的问题用矩阵树定理解决。

考虑如何解决去重的问题，也就是如何保证每个公司都修建一条道路。

用容斥来解决，为方便起见，我处理时先将\(n\)减了1。

设\(f(n)\)为用\(n\)个公司，且不考虑每个公司都修建一条道路的要求，生成树的方案数。

应用容斥公式，那么答案\(ans=\sum\limits_{i=1}^n(-1)^{n-i}f(i)\)

那么我们枚举子集，用矩阵树定理计算求解即可。

实现细节看代码吧。

\(code:\)

#include<bits/stdc++.h>

#define maxn 20

#define maxm 410

#define mod 1000000007

using namespace std;

typedef long long ll;

template<typename T> inline void read(T &x)

{

    x=0;char c=getchar();bool flag=false;

    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}

    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}

    if(flag)x=-x;

}

ll n,all,sum,cnt;

ll a[maxn][maxn];

void add(int x,int y)

{

    a[x][x]++,a[y][y]++;

    a[x][y]--,a[y][x]--;

}

struct edge

{

    int x,y;

};

struct node

{

    ll num;

    edge e[maxm];

}p[maxn];

ll det()

{

    ll ans=1;

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

    {

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

        {

            while(a[j][i])

            {

                ll d=a[i][i]/a[j][i];

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

                    a[i][k]=((a[i][k]-a[j][k]*d%mod)%mod+mod)%mod;

                swap(a[i],a[j]),ans*=-1;

            }

        }

        ans=ans*a[i][i]%mod;

    }

    return (ans%mod+mod)%mod;

}

int main()

{

    read(n),n--,all=1<<n;

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

    {

        read(p[i].num);

        for(int j=1;j<=p[i].num;++j)

            read(p[i].e[j].x),read(p[i].e[j].y);

    }

    for(int s=1;s<all;++s)

    {

        cnt=0;

        memset(a,0,sizeof(a));

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

        {

            if(s&(1<<(i-1)))

            {

                cnt++;

                for(int j=1;j<=p[i].num;++j)

                    add(p[i].e[j].x,p[i].e[j].y);

            }

        }

        sum=((sum+det()*((n-cnt)&1?-1:1))%mod+mod)%mod;

    }

    printf("%lld",sum);

    return 0;

}

巴特西

题解洛谷 P4336 【[SHOI2016]黑暗前的幻想乡】

最新文章

热门文章

巴特西

题解 洛谷 P4336 【[SHOI2016]黑暗前的幻想乡】

最新文章

热门文章

题解洛谷 P4336 【[SHOI2016]黑暗前的幻想乡】