首页 > 代码库 > K个联通块

K个联通块

2024-09-09 19:23:05   207人阅读

题意：

有一张无重边的无向图， 求有多少个边集，使得删掉边集里的边后，图里恰好有K个联通块。

 

解法：

考虑dp，$h(i,S)$表示有$i$个联通块，点集为$S$的图的个数，$g(S)$表示点集为S的连通图的个数。

所以有$h(i,S) = \sum_{S_0 \subseteq S}{h(i-1,S_0) \cdot f(S-S0)}$

$answer = \frac{h(K,ALL)}{K!}$

接下来只要求出 $g(S)$ 即可，考虑 $dp$

首先枚举一个点 $x$ ，求出所有包含 $x$ 的 $g(S)$，然后递归求去掉 $x$ 的 $g(S)$ ，直到 $S$ 为空

求包含 $x$ 的$g(S)$ 时，可以考虑用容斥来求。

$M(S)$ 表示 $S$ 集合内有多少条边。

$f(S) = 2^{M(S)} - \sum_{S_0 \subseteq S}{f(S0) \cdot 2^{M(S-S0)} }$

时间复杂度$O(K \cdot 3^n)$

 

技术分享 
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 
 5 #define N 15
 6 #define LL long long
 7 #define bit(x) (1<<(x))
 8 #define P 1000000009LL
 9 
10 using namespace std;
11 
12 int n,m,K;
13 int cnt[1<<N];
14 LL f[1<<N],all[1<<N],ansv[1<<N];
15 LL h[N][1<<N];
16 int g[N];
17 
18 int cnt_bit(int S)
19 {
20     int ans=0;
21     for(;S;S>>=1) if(S&1) ans++;
22     return ans;
23 }
24 
25 LL qpow(LL x,int n)
26 {
27     LL ans=1;
28     for(;n;n>>=1,x=x*x%P)
29         if(n&1) ans=ans*x%P;
30     return ans;
31 }
32 
33 LL calc(int S)
34 {
35     int tmp=0;
36     for(int i=0;i<n;i++)
37         if(S&bit(i)) tmp += cnt[S&g[i]];
38     return qpow(2,tmp);
39 }
40 
41 int main()
42 {
43     int Te=0;
44     int T;
45     cin>>T;
46     for(int S=0;S<(1<<N);S++) cnt[S]=cnt_bit(S);
47     while(~scanf("%d%d%d",&n,&m,&K))
48     {
49         for(int i=0;i<n;i++) g[i]=0;
50         for(int i=1,x,y;i<=m;i++)
51         {
52             scanf("%d%d",&x,&y);
53             x--;
54             y--;
55             g[x]|=bit(y);
56         }
57         for(int S=0;S<(1<<n);S++) all[S]=calc(S);
58         for(int i=0;i<n;i++)
59         {
60             ansv[0]=0;
61             for(int S=1;S<(1<<n);S++)
62                 if(S&bit(i))
63                 {
64                     f[S]=all[S];
65                     for(int S0=S;S0;S0=(S0-1)&S)
66                         if((S0&bit(i)) && S0<S)
67                         {
68                             f[S] += P - f[S0]*all[S^S0]%P;
69                             if(f[S]>=P) f[S]-=P;
70                         }
71                     ansv[S]=f[S];
72                 }
73         }
74         for(int S=0;S<(1<<n);S++) h[0][S]=0;
75         h[0][0]=1;
76         for(int i=1;i<=K;i++)
77         {
78             for(int S=1;S<(1<<n);S++)
79             {
80                 h[i][S]=0;
81                 for(int S0=S;S0;S0=(S0-1)&S)
82                 {
83                     h[i][S] += h[i-1][S^S0]*ansv[S0]%P;
84                     if(h[i][S]>=P) h[i][S]-=P;
85                 }
86             }
87         }
88         LL fac_K=1;
89         for(int i=1;i<=K;i++) fac_K=fac_K*i%P;
90         printf("Case #%d:\n",++Te);
91         cout << h[K][(1<<n)-1]*qpow(fac_K,P-2)%P << endl;
92     }
93     return 0;
94 }
View Code

 

K个联通块


联系
我们