mydcwfy's Blog

HDU4997 Biconnected

Posted on
Symbols count in article: 3.7k Reading time ≈ 8 mins.

题意：给定一个 $n$ 个点 $m$ 条边的无向图，问有多少个 $m$ 条边组成的集合使得只有这些边存在让 $n$ 个点构成一个边双连通分量。$n\leq 10$，对 $10 ^ 9 + 7$ 取模。

其实这个很难计数，因为我们不好实时判断一个边双联通分量是否存在。考虑对其进行容斥。

首先考虑一个简单的问题：让 $n$ 个点构成连通图的方案数。这个可以通过状态压缩 + 容斥解决，对于每一个集合 $S$，记连通图方案数为 $g(S)$，枚举编号最小的那个点（其实哪个点都行）所在的集合，然后就可以得到以下式子：

$f(S)$ 代表任意连边的方案数，即为 $\displaystyle 2 ^ {\sum[(u, v)\in E\land u\in S\land v\in S]}$。

这样我们可以在 $O(3 ^ n)$ 时间内求出所有的 $g(S)$，还是可以接受的。

然后我们类似于上面这种方法，计算 $h(S)$，表示 $S$ 集合内部组成一个双连通分量的方案数。

我们直接模仿上面的方法，枚举 $T$ 为最小编号所在集合，然后其他的只需要满足是连通图就可以了。但是这会带来一个问题，就是 $T$ 和 $S/T$ 之间的连边不好确定，因为需要保证 $T$ 和 $S / T$ 联通，但是 $T$ 不会和 $S / T$ 中的任何部分组成边双连通。

$n \leq 10$ 非常小，我们可以直接考虑枚举点双集合，这需要一个 Bell 数枚举所有集合划分。连通图缩点后一定是一个树，那么我们可以考虑对这个生成树进行计数。对这个生成树计数就显得更为可做，我们预先知道两两之间的连边条数，用矩阵树定理即可求解。想知道两两连边条数，我们可以直接暴力预处理计算，也可以在特定位置 +1，使用集合幂级数，或者是预处理一个点到集合的连边数，都是可以的。

时间复杂度不好估量，大概是 $O(\mathrm{Bell}(n)n ^ 3)$，可以通过就是了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
int det(int n)
{
	int res = 1, x = 0;
	for (int i = 1; i <= n; ++ i)
	{
		int t = -1;
		for (int j = i; j <= n; ++ j)
			if (a[j][i]) {
				t = j;
				break;
			}
		if (!~t) return 0;
		if (i ^ t) x ^= 1, std::swap(a[i], a[t]);
		res = (LL) res * a[i][i] % Mod;
		LL Inv = qpow(a[i][i]);
		for (int j = i; j <= n; ++ j) a[i][j] = (LL) a[i][j] * Inv % Mod;
		for (int j = i + 1; j <= n; ++ j)
			for (int k = n; k >= i; -- k)
				a[j][k] = (a[j][k] + (LL) (Mod - a[i][k]) * a[j][i]) % Mod;
	}
	return x ? adj(res = -res) : res;
}

void solve(std::vector<int> all)
{
	if (all.size() == 1) return;
	int m = all.size();
	for (int i = 1; i <= m; ++ i)
		for (int j = 1; j <= m; ++ j)
			if (i != j) a[i][j] = bew[all[i - 1]][all[j - 1]];
			else a[i][j] = 0;
	for (int i = 1; i <= m; ++ i)
	{
		int t = 0;
		for (int j = 1; j <= m; ++ j) t += a[i][j];
		for (int j = 1; j <= m; ++ j)
			if (a[i][j]) a[i][j] = Mod - a[i][j];
		a[i][i] = t;
	}
	/*for (int i = 1; i <= m; ++ i, puts(""))
		for (int j = 1; j <= m; ++ j)
			printf("%d ", a[i][j]);*/
	int ans = det(m - 1);
	for (int &x : all) ans = (LL) ans * g[x] % Mod;
	/*for (int x : all) printf("%d ", x);
	printf(": %d\n", ans);*/
	adj(res += ans - Mod);
}

void dfs(int s, std::vector<int> &all)
{
	if (!s) return solve(all);
	// std::cout << s << ' ' << all.size() << '\n';
	all.push_back(0);
	int t = ctz(s);
	for (int s2 = s; s2; s2 = (s2 - 1) & s)
	{
		if (!(s2 >> t & 1)) continue;
		all.back() = s2;
		dfs(s ^ s2, all);
	}
	all.pop_back();
}

void work()
{
	std::cin >> n >> m;
	ban.clear();
	for (int i = 1, u, v; i <= m; ++ i)
	{
		std::cin >> u >> v;
		if (u > v) std::swap(u, v);
		ban.insert({-- u, -- v});
	}

	for (int i = 0; i < n; ++ i)
		for (int j = 0; j < n; ++ j)
			if (i >= j || ban.count({i, j})) a[i][j] = 0;
			else a[i][j] = 1;
	for (int s = 0; s < (1 << n); ++ s) ins[s] = 0;
	for (int s1 = 0; s1 < (1 << n); ++ s1)
		for (int s2 = 0; s2 < (1 << n); ++ s2) bew[s1][s2] = 0;
	for (int i = 0; i < n; ++ i)
		for (int j = 0; j < n; ++ j)
			if (a[i][j]) ins[(1 << i) | (1 << j)] ++;
	for (int i = 0; i < n; ++ i)
		for (int j = 0; j < i; ++ j)
			bew[1 << i][1 << j] = bew[1 << j][1 << i] = a[j][i];

	for (int i = 0; i < n; ++ i)
		for (int s1 = 0; s1 < (1 << n); ++ s1)
			if (s1 >> i & 1)
				for (int s2 = 0; s2 < (1 << n); ++ s2)
					bew[s1][s2] += bew[s1 ^ (1 << i)][s2];
	for (int i = 0; i < n; ++ i)
		for (int s2 = 0; s2 < (1 << n); ++ s2)
			if (s2 >> i & 1)
				for (int s1 = 0; s1 < (1 << n); ++ s1)
					bew[s1][s2] += bew[s1][s2 ^ (1 << i)];
	for (int i = 0; i < n; ++ i)
		for (int s = 0; s < (1 << n); ++ s)
			if (s >> i & 1) ins[s] += ins[s ^ (1 << i)];
	
	for (int s = 1; s < (1 << n); ++ s)
	{
		f[s] = pw2[ins[s]];
		int t = ctz(s);
		for (int s2 = s & (s - 1); s2; s2 = (s2 - 1) & s)
			if (s2 >> t & 1) f[s] = (f[s] + (LL) (Mod - f[s2]) * pw2[ins[s ^ s2]]) % Mod;
	}
	std::vector<int> tmp;
	for (int s = 1; s < (1 << n); ++ s)
		res = 0, dfs(s, tmp), adj(g[s] = f[s] - res);
	// for (int s = 1; s < (1 << n); ++ s) printf("%d ", g[s]);
	std::cout << g[(1 << n) - 1] << '\n';
}