C题: Forest

原题链接:https://ac.nowcoder.com/acm/contest/33191/C

题目大意

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

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

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

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

题解

考虑枚举，显然生成子图和最小生成森林都不易枚举，不妨枚举每一条边，计算其在多少张生成子图中作为最小生成森林的边(即作贡献的次数)。

不妨将所有 $m$ 条边按照边权从小到大进行排序，考虑第 $i$ 条边 $e_i$ 的贡献 $an{s}_i$ 。
( $u_i,v_i$ 表示 $e_i$ 的两个端点， $w_i$ 表示 $e_i$ 的权值)
显然，边权大于 $w_i$ 的边(即排序后下标 $j\in [i+1,m]$ 的边)是否存在于生成子图中不会对 $e_i$ 是否作贡献造成影响，只需要在算出前 $i$ 条边组成的生成子图中 $e_i$ 的贡献次数后，乘上系数 $2^{m-i}$ ( $m-i$ 条边选/不选)即可。
(对于权值相等的边而言，因为答案计算的是权值和，故考虑谁先谁后并不影响，不需要处理相互顺序，可以任意排列)
对于边权小于 $w_i$ 的边(即排序后下标 $j\in [1,i-1]$ 的边)，当且仅当他们无法使 $u_i$ 与 $v_i$ 联通时， $w_i$ 作贡献。
不联通较难计算，正难则反，考虑稍易的 $u_i$ 与 $v_i$ 联通的生成子图数。
用状压 $dp$ 计数，设 $f_{i,S}$ 表示仅含有前 $i$ 条边的生成子图中恰有 $S$ ( $S$ 为一个二进制压缩的点集)一个连通块的方案数。
考虑从 $f_{i-1,S}$ 转移到 $f_{i,S}$ ，显然，原先每一种已经联通的方案都可以乘上系数 $2$ (第 $i$ 条边选/不选)，并且当第 $i$ 条边联通 $2$ 个原先不联通的连通块时也会产生新的方案，可得转移式如下:
$$f_{i,S}=2f_{i-1,S}+\sum _{T\subset S,u_i\in T,v_i\in S-T}{f}_{i-1,T}\ast f_{i-1,S-T}$$

然后考虑如何计算 $an{s}_i$ 。

---

辅助计数，引入 $g_{i,S}$ 表示前 $i$ 条边中端点均在点集 $S$ 中的边数。
易得转移式:
$$g_{i,S}=g_{i-1,S}+[u_i\in S\&v_i\in S]$$

---

枚举 $u_i,v_i$ 联通时所在的联通块，此时有三种边:

• 联通块内的边(已经在 $f$ 中考虑)
• 联通块连向外部节点的边(肯定不能存在，否则联通块不封闭)
• 外部节点间的边(是否存在皆可，作为系数 $2^k$ ， $k$ 为外部节点间的边数)

因而可得前 $i-1$ 条边构成联通子图中 $u_i,v_i$ 不联通的个数为
$$2^{i-1}-\sum _{S\subset V,u_i\in S,v_i\in S}{f}_{i-1,S}\ast 2^{g_{i-1,V-S}}$$

最终答案:
$$an{s}_i=w_i\ast 2^{m-i}\ast (2^i-\sum _{S\subset V,u_i\in S,v_i\in S}{f}_{i-1,S}\ast 2^{g_{i-1,V-S}})$$

---

实际上 $f$ 和 $g$ 在转移时只需要上一维，可以压缩空间，不过注意 $f$ 在转移时要延迟更新。

参考代码

#include
using namespace std;

template<class T>inline void read(T&x){
	char c,last=' ';
	while(!isdigit(c=getchar()))last=c;
	x=c^48;
	while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+(c^48);
	if(last=='-')x=-x;
}

const int N=16,M=1e2+5,P=998244353;
int n,m;
int f[(1<<N)+5],d[(1<<N)+5];
int g[(1<<N)+5];
int pw[M];
struct node{int u,v,w;}e[M];

bool cmp(node a,node b){return a.w<b.w;}

int main()
{
	read(n);
	for(int i=0;i<n;++i){
		for(int j=0,x;j<n;++j){
			read(x);
			if(i>j&&x){
				++m;
				e[m].u=i,e[m].v=j,e[m].w=x;
			}
		}
	}
	sort(e+1,e+m+1,cmp);
	for(int i=0;i<n;++i)f[1<<i]=1;//初始化,每个点单独构成联通块
	pw[0]=1;
	for(int i=1;i<=m;++i)pw[i]=pw[i-1]*2ll%P;//预处理2的幂
	int ans=0;
	for(int i=1,u,v,w;i<=m;++i){
		u=e[i].u,v=e[i].v,w=e[i].w;
		int S=(1<<n)-1;
		S^=1<<u,S^=1<<v;//先去除u和v
		int tmp=pw[i-1];
		for(int T=S;~T;T=T?T-1&S:-1){//这一行是枚举所有S的子集,~T判断T是否为-1
			tmp=(tmp-1ll*f[T|1<<u|1<<v]*pw[g[S^T]])%P;
			//T|1<
		}
		ans=(ans+1ll*w*pw[m-i]%P*tmp)%P;
		for(int T=S;~T;T=T?T-1&S:-1){//枚举S的子集
			for(int t=T;~t;t=t?t-1&T:-1){//枚举T的子集
				d[T|1<<u|1<<v]=(d[T|1<<u|1<<v]+1ll*f[t|1<<u]*f[T^t|1<<v])%P;
				//d数组用于延迟更新f,t|1<
			}
		}
		for(int T=S;~T;T=T?T-1&S:-1){//枚举S的子集
			f[T|1<<u|1<<v]=(2ll*f[T|1<<u|1<<v]+d[T|1<<u|1<<v])%P;
			d[T|1<<u|1<<v]=0;//清空
			++g[T|1<<u|1<<v];//更新g数组
		}
	}
	cout<<(ans+P)%P<<'\n';
	return 0;
}
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