P6789 题解

First Post:

Last Update:

要打开此题的突破口，Kruskal 和拆贡献都要想到。我只想到了 Kruskal ，所以寄了。大概在此种计数最优方案的题中，以已有的最优化算法为基础，进行贡献拆解是常见的套路。

类似的题还有：P4517 JSOI2018 防御网络。

对于一张确定的图，这道题是要我们求出边权和最大的基环树森林。

而基环树森林与生成树是类似的，可以套用 Kruskal 算法的模型，将边从大到小排序，如果加入一条边仍满足条件就加进去（因为 “基环树森林” 的限制可以像“生成树”一样导出一个拟阵，所以我们才能贪心地加边）。

那么我们考察某一条边 的贡献，看它什么时候会被加进去。

假设我们已经做完了边权大于 的所有边，那么这条边就面临两种产生贡献的情况：

  1. 连通，且该连通块是棵树，

  2. 不连通，且连起来的两个连通块要么是树，要么是基环树，且不都是基环树。

我们发现第二类贡献的形式非常麻烦，首先这个基环树的限制不好处理，其次我们还要讨论三种情况。

正难则反，我们考虑这条边不会产生贡献的情况。

那就是：

  1. 连通，且该连通块不是树。
  2. 不连通，且连起来的两个连通块都不是树。

对于第一类贡献，考虑算出 表示点集 的导出子图的生成树个数，这可以通过枚举子集做到 。

具体地，枚举最后加入的一条边所连接起的两个连通块 和 ，然后在连接这两个连通块的边中任选一条作为“最后加入的一条边” 即可。

为了避免重复的枚举，我们选出一个特殊点 ，钦定 包含这个点。（在很多图计数中，会看到“枚举 号点所在的连通块”，其实就是这个意思，避免算重）

（注意：类加完答案之后要除以 ，因为同一棵树会被这种方法算这么多次）

如何快速求出两个连通块之间连了多少条边？预处理 表示点集 的导出子图有多少条边，那么边数就是 。

我们还要算出 表示点集 的导出子图的连通子图的个数，这个也可以用一个容斥做到 ，即枚举特殊点 所在的连通块点集。

那么第一类贡献就很好计算了，直接枚举 所在的连通块即可。

第二类贡献也很好计算，我们枚举 分别属于哪两个连通块，设为 ，那因为一个连通块 不是树的方案数就是 ，贡献系数就是 ，因为在 外的边可以任意排布，我们还需乘上 ，其中 为全集。

注意到上面算的一直都是方案数，我们除以总数将其转为概率，再用总概率 去减即可（ 是因为当前考虑的这条边必须选）。

总时间复杂度为 ，略微卡常，需要一些剪枝。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 17,Sz = 1 << 15,M = 65,P = 998244353;
inline int Add(int a,int b) { return (a + b >= P) ? (a + b - P) : (a + b);}
inline int Sub(int a,int b) { return (a < b) ? (a - b + P) : (a - b);}
inline int qpow(int a,int b) { int res = 1;while(b) {if(b&1) res = 1ll * res * a % P;a = 1ll * a * a % P;b >>= 1;} return res;}
struct Edge{
	int u,v,w;
	Edge(){}
	Edge(const int _u,const int _v,const int _w):
		u(_u),v(_v),w(_w){}
	bool operator < (const Edge &rhs) const { return w > rhs.w;}
};
int n,m;
Edge e[M];
int f[Sz],g[Sz];
int pop[Sz];
int cnt[Sz]; // 每个点集的导出子图的边数
int Pow2[M];
int inv[N];
int Solve(int x) // 当前扫到第 x 条边
{
	memset(cnt,0,sizeof cnt);
	for(int i = 1;i < x;i++)
		++cnt[(1 << e[i].u) | (1 << e[i].v)];
	for(int j = 0;j < n;j++)
		for(int i = 0;i < (1 << n);i++)
			if((i >> j) & 1)
				cnt[i] += cnt[i ^ (1 << j)];
	f[0] = g[0] = 0;
	int all = (1 << n) - 1;
	for(int S = 1;S <= all;++S)
	{
		if(pop[S] == 1) {f[S] = g[S] = 1;continue;}
		if(cnt[S] < pop[S] - 1) { f[S] = g[S] = 0;continue;}
		f[S] = 0;g[S] = Pow2[cnt[S]];
		int z = S & (-S),w = S ^ z;
		for(int T = w;T;T = (T - 1) & w)
		{
			int bu = S ^ T,num = cnt[S] - cnt[T] - cnt[bu]; // bu 中包含了特殊点 z
			f[S] = Add(f[S], 1ll * f[T] * f[bu] % P * num % P);
			g[S] = Sub(g[S],1ll * g[bu] * Pow2[cnt[T]] % P);
		}
		f[S] = 1ll * f[S] * inv[pop[S] - 1] % P;
	}
	for(int S = 1;S <= all;++S)
		g[S] = Sub(g[S],f[S]);
	int res = 0;
	int u = 1 << e[x].u,v = 1 << e[x].v;
	for(int S = 1;S <= all;++S)
	{
		if(!(S & u) || !(S & v)) continue;
		res = Add(res,1ll * g[S] * Pow2[cnt[all ^ S]] % P);
	}
	// 第二类贡献
	for(int A = 1;A <= all;++A)
	{
		if((A & v) || !(A & u)) continue;
		int buA = all ^ A;
		for(int B = buA;B;B = (B - 1) & buA)
		{
			if(!(B & v)) continue;
			res = Add(res,1ll * g[A] * g[B] % P * Pow2[cnt[all ^ A ^ B]] % P);
		}
	}
	int allp = (P + 1) / 2;
	res = 1ll * res * qpow(Pow2[x],P - 2) % P;
	res = Sub(allp,res);
	res = 1ll * res * e[x].w % P;
	return res;
}
int main()
{
	cin >> n >> m;
	for(int i = 1;i <= m;i++)
	{
		cin >> e[i].u >> e[i].v >> e[i].w;
		--e[i].u;--e[i].v;
	}
	sort(e + 1,e + m + 1);
	
	for(int i = 1;i < (1 << n);i++) pop[i] = pop[i >> 1] + (i & 1);
	Pow2[0] = 1;
	for(int i = 1;i <= m;i++) Pow2[i] = 2ll * Pow2[i - 1] % P;
	inv[1] = 1;
	for(int i = 2;i <= n;i++) inv[i] = 1ll * inv[P % i] * (P - P / i) % P;
	int ans = 0;
	for(int i = 1;i <= m;i++)
		ans = Add(ans,Solve(i));
	cout << ans << endl;
	return 0;
}
≡