HDOJ 4997 - Biconnected

Published on 2016-06-11

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

描述

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

分析

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

我们先求 cons{con}_s

cons=2edges[s][s]lowbit(s)s1,s1scons1×2edges[ss1][ss1]{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]}

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

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

mer[s][s1]=lowbit(s)s2,s2sbcons2×edges[s2][s1]×mer[ss2][s1]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]

思路还是枚举标号最小的点所在双联通分量 s2s_2,将其接到 s1s_1 上面,再将剩余的部分 ss2s - s_2 接到 s1s_1 上去。
scons{scon}_s 可以求了:

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

最后 bcons=consscons{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;
}