bzoj2560

题意

n个不同的点,标号(1~n),$c[i][j]$:表示$i$与$j$两点之间的不同的边数。

现在问有多少种连边方案可以使得n个点连通? 答案模$1e^9+7$

两点之间最多连一条边。

$n \leq 20$

分析

即求无向连通图的个数

大致思路:

设$S$表示一些点的集合,$all[S]$表示当前集合内所有连边的可能性。$dp[S]$表示当前集合内的所有点是一个联通块的连边方案数。 那么用$all[S]$减去$S$中不连通的情况就是$dp[S]$。

那么怎么求$S$中不连通的情况数呢?

为了防止重复,我们规定$S$中的某个点为标志点,那么剩下的点可以分为两部分:一部分和标志点连通记为$A$,另一部分和标志点不连通记为$B$。

那么$dp[S] = all[S] - dp[A] * all[B]$

即与标志位连通的集合的方案数和与标志不连通的集合的所有可能情况。

复杂度:$O(3^n)$

代码

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
// ybmj
#include <bits/stdc++.h>
using namespace std;
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define lson_len (len - (len >> 1))
#define rson_len (len >> 1)
#define pb(x) push_back(x)
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define my_unique(a) a.resize(distance(a.begin(), unique(a.begin(), a.end())))
#define my_sort_unique(c) (sort(c.begin(), c.end())), my_unique(c)
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const double PI = acos(-1.0);
const int maxn = 1 << 21;
const int mod = 1e9 + 7;
ll a[20][20], all[maxn], dp[maxn];
int main() {
// /*
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
// */
std::ios::sync_with_stdio(false);
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) scanf("%lld", &a[i][j]);
for (int i = 1; i < (1 << n); i++) {
all[i] = 1;
for (int j = 0; j < n; j++)
if (i & (1 << j))
for (int k = j + 1; k < n; k++)
if (i & (1 << k)) all[i] = all[i] * (a[j][k] + 1) % mod;
int s; // 标志点
for (int j = n - 1; j >= 0; j--)
if (i & (1 << j)) {
s = j;
break;
}
dp[i] = all[i];
s = i ^ (1 << s); // 不包含标志点的集合
for (int j = s; j; j = (j - 1) & s) { // 子集枚举
dp[i] = (dp[i] - all[j] * dp[i ^ j] % mod + mod) % mod;
}
}
printf("%lld\n", dp[(1 << n) - 1]);
}