题解：P6238 [JSOI2011] 序的计数

· · 题解

P6238 [JSOI2011] 序的计数题解

思路：

首先构建一个新的虚拟节点连接所有目标节点，强行将其作为第一个被访问的节点，这样子就解决了图不连通的问题。

除了目标节点外，所有其他点都可以缩成一个节点。

这样子的图实际上只有 k + 2 个节点， k + 1 个目标节点。

预处理 G[S][u] 表示已经在 dfs 序中出现过的点的集合为 S， 当前在点 u 能够访问到的点。

设 f[S][u] 表示当前在点 u ，已经确定 dfs 序的集合为 S 的 dfs 序的方案数。

注意如果一个点和不合法的点有连边，那么这个点不能回朔。

转移的时候枚举一个 u 的相邻点，记忆化搜索即可。

Code：

#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
#define MAXN 120
using namespace std;
inline int read() {
    int x = 0;
    bool t = false;
    char ch = getchar();
    while ((ch < '0' || ch > '9') && ch != '-')ch = getchar();
    if (ch == '-')t = true, ch = getchar();
    while (ch <= '9' && ch >= '0')x = x * 10 + ch - 48, ch = getchar();
    return t ? -x : x;
}
int n, m, K, id[MAXN], S[20];
bool g[MAXN][MAXN], M[20][20];
ll f[1 << 19][20];
int G[1 << 19][20];
int dfs(int u, int S) {
    if (~G[S][u])return G[S][u];
    int ret = 1 << u;
    for (int i = 0; i < K; ++i)
        if (M[u][i] && !(S & (1 << i)))ret |= dfs(i, S | (1 << i));
    return G[S][u] = ret;
}
ll Solve(int u, int S) {
    if (~f[S][u])return f[S][u];
    if (G[S][u] == 1 << u)return S == (1 << K) - 1 || !M[u][K];
    ll ret = 0;
    for (int i = 0; i < K; ++i)
        if (M[u][i] && !(S & (1 << i)))
            ret += Solve(i, S | (1 << i)) * Solve(u, S | G[S | (1 << i)][i]);
    return f[S][u] = ret;
}
int main() {
    n = read();
    m = read();
    K = read();
    K += 1;
    for (int i = 1, u, v; i <= m; ++i)u = read(), v = read(), g[u][v] = g[v][u] = 1;
    for (int i = 1; i <= n; ++i)id[i] = K;
    for (int i = 0; i < K - 1; ++i)S[i] = read(), id[S[i]] = i, M[i][K - 1] = M[K - 1][i] = 1;
    for (int i = 0; i <= K; ++i)
        for (int j = 1; j <= n; ++j)M[i][id[j]] |= g[S[i]][j];
    memset(G, -1, sizeof(G));
    memset(f, -1, sizeof(f));
    for (int i = 0; i < (1 << K); ++i)
        for (int j = 0; j < K; ++j)
            if (i & (1 << j))dfs(j, i);
    printf("%lld\n", Solve(K - 1, 1 << (K - 1)));
    return 0;
}