HDOJ 4997 - Biconnected | Sengxian's Blog

HDOJ 4997 - Biconnected

#DP #计数

Published on 2016-06-11

题目地址
出处：「陈立杰－计数问题选讲」
百度文库显示 beamer 排版的 PPT 画质很有问题，下载下来就好了。

描述

给你一个 $n(2\le n \le 10)$ 个点的无向简单图,问有多少个边的子集 ,使得只保留中的边的话,整个图是边-双联通的。也就是问你有多少个关于边的子图（点集合还是这 $n$ 个点）边-双连通。
P.S: 虽然 Biconnected 一般是表示点-双联通，但这里的确是边-双联通。

分析

边-双联通的子图数量 $bcon$ 貌似看起来极不好求，那么我们就用联通的子图数量 $con$ 减去单联通的子图数量 $scon$ 。可以使用状态压缩 DP 求解。
会用到的一些东西：
$ecnt[s_1][s_2]$ 为点集合 $s_1$ 到点集合 $s_2$ 的边的数量（同一条边只算一次）。
${con}_s$ 只保留原图中 $s$ 这些点形成的图的子图中联通图的数量。
${scon}_s$ 只保留原图中 $s$ 这些点形成的图的子图中单联通图的数量。
${bcon}_s$ 只保留原图中 $s$ 这些点形成的图的子图中边-双联通图的数量。
$mer[s][s_1]$ 表示将 $s$ 分为若干个联通的边双联通分量，连边到双联通分量 $s_1$ 的方案数目。
$\text{lowbit}(s)$ 表示 $s$ 中最小的元素。

我们先求 ${con}_s$ ：

{con}_s = 2^{edges[s][s]} - \sum\limits_{\text{lowbit}(s) \in s_1, s_1\subset s}{con}_{s_1}\times2^{edges[s - s_1][s - s_1]}

转移的思路在于枚举标号最小的点所在联通块的情况，剩余点的随便连得到不联通图的数量。再用任意图的数量减去不联通图的数量即得联通图的数量。

接着要算 ${scon}_s$ ，不难发现，单联通的图一定是由若干双联通分量组成的一棵树，和之前一样，我们可以枚举标号最小的点所在的双联通分量，由于整个图要联通，需要将这个将这个联通块与剩余的合并（显然不同的合并方案对应不同的图）。
我们先解决合并的方案问题：

mer[s][s_1] = \sum_{\text{lowbit}(s) \in s_2, s_2\subseteq s}{bcon}_{s_2}\times edges[s_2][s_1]\times mer[s - s2][s_1]

思路还是枚举标号最小的点所在双联通分量 $s_2$ ，将其接到 $s_1$ 上面，再将剩余的部分 $s - s_2$ 接到 $s_1$ 上去。
则 ${scon}_s$ 可以求了：

{scon}_s = \sum_{\text{lowbit}(s) \in s_1, s_1\subseteq s}{bcon}_{s_1}\times mer[s - s_1][s_1]

最后 ${bcon}_s = {con}_s - {scon}_s$ 。

总结：这对我来说真是个难题。

代码

//  Created by Sengxian on 6/11/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  HDOJ 4997 双联通子图计数
#include <algorithm>
#include <iostream>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;

inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}
typedef long long ll;
const int maxn = 10, modu = 1000000007;
ll con[1 << maxn], scon[1 << maxn], bcon[1 << maxn], mer[1 << maxn][1 << maxn];
int n, m, ecnt[1 << maxn][1 << maxn], powers[maxn * maxn];
bool G[maxn][maxn];

int ALL;

void solve(const int s) {
    int lowbit = s & -s;
    //计算联通图的数量
    con[s] = powers[ecnt[s][s]];
    for (int s1 = s ^ lowbit; s1; s1 = (s1 - 1) & s) if (s1 & lowbit)
        (con[s] -= con[s1] * powers[ecnt[s ^ s1][s ^ s1]] % modu) %= modu;

    //mer[s][s1] 将 s 分成若干个双联通块连边到 s1 的方案数
    mer[0][s] = 1;
    for (int s1 = s ^ lowbit; s1; s1 = (s1 - 1) & s) { //枚举非根的部分，方便后面的枚举
        int low1 = s1 & -s1;
        for (int s2 = s1; s2; s2 = (s2 - 1) & s1) if (s2 & low1)
            (mer[s1][s - s1] += mer[s1 - s2][s - s1] * con[s2] % modu * ecnt[s2][s - s1]) %= modu;
    }
    //计算联通度为 1 的图的数量
    for (int s1 = s ^ lowbit; s1; s1 = (s1 - 1) & s) if (s1 & lowbit)
        (scon[s] += bcon[s1] * mer[s - s1][s1] % modu) %= modu;

    bcon[s] = (con[s] - scon[s] + modu) % modu;
}

int main() {
    powers[0] = 1;
    for (int i = 1; i < maxn * maxn; ++i) powers[i] = (powers[i - 1] << 1) % modu;
    int caseNum = ReadInt();
    while (caseNum--) {
        n = ReadInt(), m = ReadInt();
        ALL = (1 << n) - 1;
        memset(G, 0, sizeof G);
        memset(con, 0, sizeof con);
        memset(scon, 0, sizeof scon);
        memset(bcon, 0, sizeof bcon);
        memset(mer, 0, sizeof mer);
        memset(ecnt, 0, sizeof ecnt);
        for (int i = 0, f, t; i < m; ++i) {
            f = ReadInt() - 1, t = ReadInt() - 1;
            G[f][t] = G[t][f] = 1;
        }
        for (int i = 0; i < n; ++i) G[i][i] = 1; //没有自环
        for (int s = 0; s <= ALL; ++s)
            for (int s1 = 0; s1 <= ALL; ++s1) if (s == s1 || (s & s1) == 0)
                for (int i = 0; i < n; ++i)    if ((s >> i) & 1)
                    for (int j = s == s1 ? i + 1 : 0; j < n; ++j) if ((s1 >> j) & 1)
                        ecnt[s][s1] += !G[i][j];
        for (int i = 0; i <= ALL; ++i) solve(i);
        printf("%lld\n", (bcon[ALL] + modu) % modu);
    }
    return 0;
}

BZOJ 3812 - 主旋律 BZOJ 3928 - [Cerc2014] Outer space invaders