【CF53E】Dead Ends 题解

· · 题解

本篇题解是直接状压 dp 题解，内容不含容斥和矩阵树定理。

其他的题解里大多有写到防止算冲，却没有任何一篇题解讲明白如何防止，为什么这样做可以做到不算重。于是我这篇题解就来补充一下证明。

首先我们来设计状态，我们从只有节点 1 开始 f_{S1,S2} 表示集合 S1 已经与节点 1 联通，其中 S2 集合是度数为一的节点，每次都选一条边 (u,v)，u 在 S1 中，v 不在 S1 中，然后将 v 加入 S1，S2，若 u 在 S2 中则从 S2 中删去 u，进行状压 dp 。

但这样有一个问题，这样有可能会算重，例如样例一中选择 (1,2)(1,3) 会被加入两次。

如何才能防止算重呢？我们发现状压 dp 表示的其实是一个在生成树中不断加边的过程，也就是说，如果能做到让生成树能且仅能通过一种加边顺序形成，就能算出答案。

解决方法是：当新加入一个叶子节点是，判断它是否为所有当前叶子节点中序号最大的节点，若是则进行转移，否则不进行转移。

证明：对于一棵生成树，必须先把节点 1 到节点 2 的路径上的边依次加入，再把节点 1 到节点 3 的路径上未被加入的边依次加入，以此类推直到节点 1 到节点 n 路径上所有边已被加入。这种加边方式显然是会被计算到的，但是如果不这样加边，比如在加入节点 1 到节点 v 的过程中加入了其他的边，则当 v 被加入时，必然有一个比它编号大的节点，是不会被重复计算的。

代码就比较好写了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f[1<<10][1<<10],ans;
int n,m,d;
bool g[11][11];
int main()
{
    scanf("%d%d%d",&n,&m,&d);
    for(int i = 1,u,v;i <= m;i++)
    {
        scanf("%d%d",&u,&v);
        g[u][v] = g[v][u] = 1;
    }
    for(int i = 2;i <= n;i++)
        if(g[1][i]) f[1<<(i-1)|1][1<<(i-1)|1] = 1;
    for(int i = 0;i < (1<<n);i++)
    {
        for(int j = i;j;j = (j-1)&i)
        {
            if(!f[i][j]) continue;
            int c1 = 0,c2 = 0;
            for(int k = 1;k <= n;k++)
            {
                bool p1 = i&(1<<(k-1)),p2 = j&(1<<(k-1));
                if(p2) c1++;
                else if(p1) c2++;
                else continue;
                for(int l = 1;l <= n;l++)
                {
                    bool p = i&(1<<(l-1));
                    if(p||!g[l][k]) continue;
                    int to;
                    if(p2) to = j^(1<<(l-1))^(1<<(k-1));
                    else to = j^(1<<(l-1));
                    if((to>>(l-1))==1) f[i|(1<<(l-1))][to] += f[i][j];
                }
            }
            if(c1 == d && c2 == n-d) ans += f[i][j];
        }
    }
    printf("%lld\n",ans);
    return 0;
}