自动搬运

查看原文

来自洛谷，原作者为

	Soulist 再见了

搬运于2025-08-24 22:24:01，当前版本为作者最后更新于2020-10-21 23:08:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

给定 $n$ 个点 $m$ 条边的图，第 $i$ 条边的权值为 $w_i$，每条边有 $\frac{1}{2}$ 的概率被保留，求最后这张图的最大基环树森林的边权和。

Solution

$\mathcal O(2^m\cdot m\alpha(n))$ 是显然的。

类比一下 Kruskal 求 MST 就会做了。

考虑优化，我们不妨考虑判定一条边什么情况下不会被加入答案，等价于仅考虑边权大于他的边，有他连接的两个点：

1. 连通，且此时不为树。
2. 不连通，此时这两个点分别在一个基环树上。

第一类贡献很简单，我们统计仅保留这些边时点集 $S$ 的生成树的数量。这个可以枚举子集 $T\subseteq S$，然后计算一棵生成树，不难发现每棵生成树会被计算 $|S|-1$ 次，除掉即可。

统计 $T\to T\land S$ 中的边数通过 $cnt_S-cnt_T-cnt_{T\land S}$ 来计算，这样复杂度为 $\mathcal O(m\cdot 3^n)$，需要适当减枝，比如点集 $S$ 的边数小于 $|S|-1$ 时就直接 out

接下来考虑统计第二类贡献。

不难发现第二类贡献等价于点集 $A$ 和点集 $B$ 满足 $x\in A,y\in B$ 且 $A$ 是联通图不是生成树，$B$ 是联通图不是树。

枚举 $A,B$ 的总量是 $3^n$ 的，这样只需要预处理联通图计数，经典的容斥手段可以做到 $\mathcal O(3^n)$

最后，我们在 $\mathcal O(m3^n)$ 的复杂度解决了此问题。

• 预处理 $cnt$ 数组我是用高维前缀和算的。

ps : 看着不能过，但实际上有一些细节可以减一下枝，大概可以减少 $\frac{1}{3}\sim \frac{1}{9}$ 不等的常数，然后我 UB 了调了一晚上...

$Code:$

#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
#define int long long
int gi() {
	char cc = getchar() ; int cn = 0, flus = 1 ;
	while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
	while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;
	return cn * flus ;
}
const int P = 998244353 ; 
const int N = (1 << 16) + 5 ; 
int n, m, limit, bit[N], ip[N], fac[70], iv[35], f[N], g[N], cnt[N], Ans ; 
struct E {
	int u, v, w ; 
} e[100] ;
bool cmp(E x, E y) { return x.w > y.w ; }
int fpow(int x, int k) {
	int ans = 1, base = x ;
	while(k) {
		if(k & 1) ans = 1ll * ans * base % P ;
		base = 1ll * base * base % P, k >>= 1 ;
	} return ans ;
}
void inc(int &x, int y) { ((x += y) >= P) && (x -= P) ; }
void solve(int x) {
	memset( cnt, 0, sizeof(cnt) ), memset( f, 0, sizeof(f) ), memset( g, 0, sizeof(g) ) ;
	rep( i, 1, x - 1 ) ++ cnt[(1 << e[i].u) | (1 << e[i].v)] ;
	for(re int k = 1; k <= limit; k <<= 1 )
	rep( i, 0, limit ) if(i & k) cnt[i] += cnt[i ^ k] ; 
	rep( S, 1, limit ) {
		if( bit[S] == 1 ) { f[S] = g[S] = 1 ; continue ; }
		if( cnt[S] < bit[S] - 1 ) { f[S] = 0 ; g[S] = 0 ; continue ; }
		int w = (1 << ip[S]), z = S ^ w ; f[S] = 0, g[S] = fac[cnt[S]] ; 
		for(re int i = z; i; i = (i - 1) & z) {
			int u = i ^ S, t = cnt[S] - cnt[i] - cnt[u] ; 
			f[S] = (f[S] + 1ll * f[i] * f[u] % P * t ) ;
			g[S] = (g[S] - g[u] * fac[cnt[i]] % P) ; 
		}
		f[S] %= P, g[S] = (g[S] % P + P) % P ; 
		f[S] = f[S] * iv[bit[S] - 1] % P ; 
	}
	int ans = 0, u = (1 << e[x].u), v = (1 << e[x].v) ;
	rep( S, 1, limit ) g[S] = (g[S] % P - f[S] % P + P) % P ; 
	rep( S, 1, limit ) {
		if( (!(S & u)) || (!(S & v)) ) continue ; 
		int d = g[S] ; d = d * fac[cnt[limit ^ S]] % P ;
		ans = (ans + d) % P ;
		//S 联通且不为树，枚举 S，外部任意 
	}
	rep( A, 1, limit ) {
		if( (!(A & u)) || (A & v) ) continue ; 
		int T = A ^ limit ; 
		for(re int B = T; B; B = (B - 1) & T) {
			if( !(B & v) ) continue ; 
			ans = (ans + 1ll * g[A] * g[B] % P * fac[cnt[limit ^ A ^ B]] % P) % P ; 
		}
	} 
	int ffv = (P + 1) / 2 ; 
	ans = ans * fpow( fac[x], P - 2 ) % P, ans = (ffv - ans + P) % P ; 
	Ans = (Ans + ans * e[x].w) % P ; 
}
signed main()
{
	n = gi(), m = gi() ; 
	rep( i, 1, m ) 
		e[i].u = gi() - 1, e[i].v = gi() - 1, e[i].w = gi() ; 
	sort(e + 1, e + m + 1, cmp), iv[0] = fac[0] = 1 ; 
	rep( i, 1, n ) iv[i] = fpow(i, P - 2) ; 
	rep( i, 1, m ) fac[i] = fac[i - 1] * 2 % P ;
	limit = (1 << n) - 1 ; 
	rep( i, 1, limit ) {
		bit[i] = __builtin_popcountll(i) ; 
		rep( j, 0, n - 1 ) if((1 << j) & i) { ip[i] = j ; break ; }
	}
	rep( i, 1, m ) solve(i) ; 
	cout << (long long)Ans << endl ; 
	return 0 ;
}