Sandy and Nuts

题意：

现在有一个$n$个点的树形图被拆开，现在你知道其中$m$条边，已经$q$对点的$LCA$，试求原先的树有多少种可能。

解法：

考虑$dp$，$f(x,S)$表示$x$的子树内的点集为$S$（不包括$x$的方案数）

$S$被拆成$S_0 ,S_1, S_2 ... S_m$，每个集合

这样考虑$LCA(a,b) =c$，与$<x,y> ∈ E$对$dp$的影响。

前者相当于$a,b$分属于两个$S_i$，

假设$x$连向的点为$y_0,y_1...$，

后者相当于不存在$S_i$中含有两个$y_i$ 且当$S_i$中含有一个$y_i$时，必须要将$y_i$作为$S_i - \{ y_i \}$的父节点。

这样，由于每一层要背包，还要状态压缩，代码十分的复杂。

考虑类比转二叉树的方法，$f(x,S)$ 由 $f(x,S \oplus S0) \cdot f(p, S0 \oplus p)$ 转移过来。

这样代码会简化许多。

枚举子集的时候应用 $ S_0 = S \& (S_0-1)$ 的技巧。

这样，总复杂度 $O(n*3^n + q*n*2^n )$。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <vector>

 #define N 14

 #define LL long long

 #define bit(x) (1<<(x))

 using namespace std;

 int n,m,q;

 int g[N];

 LL f[N][<<N];

 vector<int> LCA[N];

 int get_bit(int S)

 {

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

         if(S&bit(i)) return i;

     return -;

 }

 int cnt_bit(int S)

 {

     int ans=;

     for(;S;S>>=) if(S&) ans++;

     return ans;

 }

 bool check(int x,int S)

 {

     for(int i=;i<(int)LCA[x].size();i++)

         if((S&LCA[x][i]) != LCA[x][i]) return ;

     return ;

 }

 LL dp(int x,int S)

 {

     if(f[x][S]!=-) return f[x][S];

     if(!S) return f[x][S] = ;

     f[x][S]=;

     int t=get_bit(S);

     for(int S0=S;S0;S0=(S0-)&S)

         if(S0&bit(t))

         {

             bool flag=;

             for(int i=;i<(int)LCA[x].size();i++)

                 if((S0&LCA[x][i]) == LCA[x][i]){flag=; break;}

             if(flag || cnt_bit(g[x]&S0)>) continue;

             int tmp=get_bit(g[x]&S0);

             if(tmp!=-)

             {

                 if(check(tmp,S0) && ( (S0|bit(x)) & g[tmp] ) == g[tmp])

                     f[x][S] += dp(x,S^S0)*dp(tmp,S0^bit(tmp));

             }

             else

             {

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

                     if(S0&bit(i))

                     {

                         if(check(i,S0) && (S0&g[i]) == g[i])

                             f[x][S] += dp(x,S^S0)*dp(i,S0^bit(i));

                     }

             }

         }

     return f[x][S];

 }

 int main()

 {

     while(~scanf("%d%d%d",&n,&m,&q))

     {

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

         {

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

                 f[i][j]=-;

             g[i]=;

             LCA[i].clear();

         }

         for(int i=,x,y;i<=m;i++)

         {

             scanf("%d%d",&x,&y);

             x--,y--;

             g[x]|=bit(y);

             g[y]|=bit(x);

         }

         for(int i=,x,y,z;i<=q;i++)

         {

             scanf("%d%d%d",&x,&y,&z);

             x--,y--,z--;

             LCA[z].push_back(bit(x)|bit(y));

         }

         cout << dp(,((<<n)-)^) << endl;

     }

     return ;

 }

巴特西

Sandy and Nuts

最新文章

热门文章