2022牛客多校#6 C. Forest

题目大意

给定 $n(1\le n\le 16)$ 个点 $m(0\le m\le 100)$ 条正边权的无向简单图，求每个生成子图的最小生成森林的权值和，答案对 $998244353$ 取模。

定义点集 $V$ ，边集 $E$ 的图 $G$ 的最小生成森林为：

• 最小生成森林的边集 $S\subseteq E$ 。
• 任意两个节点的连通性不变
• $S$ 为满足以上条件的最小权值。

图 $G$ 的生成子图为具有点集 $V$ 和边集为 $E$ 的子集所构成的图。

题解

类似题目 P6789 。

单独考虑按边权值从小到大枚举每条边的贡献，边权值第 $i$ 小的边为 $e_i=(u_i,v_i,w_i)$ 。
由于求所有方案的总权值和，因此边权值相同的边任意排序后不影响结果。

定理：

• 一条边在生成子图的最小生成森林中，当且仅当该子图中其他权值更小的点不能使得两端联通。

对于边 $e_i=(u_i,v_i,w_i)$ ，求有多少生成子图的最小生成森林包含该边。

边编号在 $[i+1,m]$ 范围内的边，不影响 $e_i$ 的选取，方案数为 $2^{m-1-i}$ 。

考虑边编号在 $[1，i-1]$ 范围内的边。
设边编号在 $[1,i-1]$ 范围内，且端点均在点集 $S$ 内的边数为 $Cn{t}_{i-1}(S)$ ，有转移式
$$Cn{t}_i(S)=[u_i\in S\&v_i\in S]+Cn{t}_{i-1}(S)$$

设边编号在 $[1,i-1]$ 范围的边构成连通块 $S$ ，则

1. 两端在 $S$ 外的边，可以任意选取。方案数为 $2^{Cn{t}_{i-1}(V-S)}$ ；
2. 只有一段在 $S$ 内的边，均不能选取，否则连通块就不是 $S$ 了。方案数为 $1$ ；
3. 两端都在 $S$ 内的边，有一部分需要被选取使得构成连通块 $S$ 。设方案数为 $f_{i-1}(S)$ ；

考虑计算 $f_{i-1}(S)$ ，等于总方案数-至少有两个连通块的方案数。
可以直接计算，枚举 $S$ 中包含编号最小的节点的连通块 $T$ ，则剩余部分为 $S-T$ ，有
$$f_{i-1}(S)=2^{Cn{t}_{i-1}(S)}-\sum _{T\subset S,lowbit(S)=lowbit(T)}{f}_{i-1}(T)\cdot 2^{Cn{t}_{i-1}(S-T)}$$

上式的复杂度为 $O(3^n)$ ，搭配枚举 $m$ ，复杂度为 $O(3^{n}m)$ ，约 4e9 ，勉强可以计算出结果。

边 $e_i$ 的贡献为
$$W_i=w_i\times (2^{m-1}-2^{m-i-1}\times \sum _{S\subseteq V,u_i\in S,v_i\in S}{2}^{Cn{t}_{i-1}(V-S)}{f}_{i-1}(S))$$

也可以考虑加入 $e_i$ 边，从 $f_{i-1}(S)$ 递推到 $f_i(S)$ ，有
f i ( S ) = { 2 f i − 1 ( S ) + ∑ T ⊂ S , u i ∉ T , v i ∉ T f i − 1 ( S − T − v i ) ⋅ f i − 1 ( T + u i ) u i ∈ S , v i ∈ S f i − 1 ( S ) o t h e r s f_i(S)=

fi​(S)={2fi−1​(S)+∑T⊂S,ui​∈/T,vi​∈/T​fi−1​(S−T−vi​)⋅fi−1​(T+ui​)fi−1​(S)​ui​∈S,vi​∈Sothers​

总复杂度 $O(m\cdot 3^{n-2})$ ，约4e8。

参考代码

来自杭电6队

#include
#define ll long long
using namespace std;
const int N=20;
const int mod=998244353;
struct node{
	int u,v,s;
};
vector<node>w;
bool operator<(const node&x,const node&y){
	return x.s<y.s;
}
int n;
int a[N][N],f[1<<N],g[1<<N],fac[1000],sum[1<<N];
int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
int dec(int x,int y){return x-y<0?x-y+mod:x-y;}
int mul(int x,int y){return (ll)x*y%mod;}
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++) scanf("%d",&a[i][j]);
	}
	for (int i=1;i<=n;i++) 
		for (int j=i+1;j<=n;j++)if (a[i][j]){
			node t; t.u=i; t.v=j; t.s=a[i][j];
			w.push_back(t);
		}
	sort(w.begin(),w.end());
	for (int i=1;i<=n;i++) f[1<<(i-1)]=1;
	fac[0]=1;
	for (int i=1;i<=500;i++) fac[i]=mul(fac[i-1],2);
	int m=(1<<n)-1,ans=0;
	for (int i=0;i<w.size();i++){
		int u=w[i].u,v=w[i].v; u--;v--;
		int t=(1<<n)-1;
		t^=(1<<u);
		t^=(1<<v);
		int s=fac[i];
		for (int j=0;j<(1<<n);j++) if ((j&(1<<u))&&(j&(1<<v))) s=dec(s,mul(f[j],fac[sum[m^j]]));
		ans=add(ans,mul(mul(s,w[i].s),fac[(int)w.size()-i-1]));
		for (int j=t;~j;j=(j?((j-1)&t):-1))
			for (int k=j;~k;k=(k?((k-1)&j):-1)) {
			g[j|(1<<u)|(1<<v)]=add(g[j|(1<<u)|(1<<v)],mul(f[(j^k)|(1<<u)],f[k|(1<<v)]));
			}
		for (int j=0;j<=m;j++){
		if ((j&(1<<u))&&(j&(1<<v))) f[j]=mul(f[j],2);
		f[j]=add(f[j],g[j]); g[j]=0;
		}
		for (int j=0;j<(1<<n)-1;j++) if ((j&(1<<u))&&(j&(1<<v))) sum[j]++; 
	}
	printf("%d\n",ans);
}
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