[DP记录]P6789 寒妖王
command_block
2021-10-21 07:42:19
**题意** ： 给定 $n$ 个点 $m$ 条边的无向图，边有边权。
每条边有 $1/2$ 的概率被删除，求最后这张图的最大基环树森林（可以有普通树）的边权和的期望。
答案对 $998244353$ 取模。
$n\leq 15,m\leq 60$ ，时限$\texttt{2s}$。
------------
计算各个方案的权值和然后除以 $2^m$ 即可。
注意到“生成基环树”这一限制和“生成树”这一限制都具有拟阵性质，于是用类似 Kruskal 的算法可以求解“最大生成基环森林”。
于是我们就得到了 $O(2^m{\rm poly}(m))$ 的暴力。
不妨设边权互不相等，将边权从大到小排序，对每条边 $l_i:(u,v)$ 分别考虑不被加入答案的充要条件。
考虑比这条边权值更大的边集 $l_{1\sim i-1}$ ：
- 这条边两侧是同一个基环树。（即联通，但不是一棵树）
- 这条边两侧是两个不同的基环树。
对于第一类情况，正难则反，枚举边 $u,v$ 所在的点集 $S\supseteq \{u,v\}$ ，用构成极大连通图的方案数减去构成极大生成树的方案数。
记 $f_{i,S},g_{i,S}$ 分别表示只考虑编号 $\geq i$ 的，且与点集 $S$ 有交（而非完全包含）的所有边，使得 $S$ 形成极大 连通图/树 的方案数。
（换句话说，若某种方案 $S,U-S$ 之间有边，不会被计入 ，因为不是极大的）
- 对于 $S\supseteq \{u_1,v_i\}$ 的 $S$ ，有转移 ：
$$f_{i,S}=2f_{i-1,S}+\sum\limits_{u_i\in A,v_i\in B,A+B=S}f_{i-1,A}f_{i-1,B}$$
$$g_{i,S}=g_{i-1,S}+\sum\limits_{u_i\in A,v_i\in B,A+B=S}g_{i-1,A}g_{i-1,B}$$
分两类讨论，不加入或加入。其中连通图内部多边没关系，但是树内部不能多边。
- 若 $u_i,v_i$ 都不在 $S$ 内，由定义，不考虑这条边，无贡献。
- 若 $u_i,v_i$ 其中之一在 $S$ 内，考虑这条边，但一旦这条边出现， $S$ 必不是极大联通块，仍无贡献。
第一类方案数为
$$\sum_{S}2^{out_{i-1,S}}(g_{i-1,S}-f_{i-1,S})$$
其中 $out_{i,S}$ 为 $l_{1\sim i}$ 中与 $S$ 不交的边数，即考虑其余边的加入情况。
第二类方案数需要枚举 $S$ 并拆成两个不交的集合，为
$$\sum_{S}2^{out_{i-1,S}}\sum\limits_{u_i\in A,v_i\in B,A+B=S}(f_{i-1,A}-g_{i-1,A})(f_{i-1,B}-g_{i-1,B})$$
记两类方案总数为 $o$ ，注意前面的边方案数为 $2^{i-1}$ ，后面的边方案数为 $2^{m-i}$ ，于是 $l_i$ 被计入的总方案数为 $2^{m-i}(2^{i-1}-o)$ 。
复杂度为 $O(3^n*m)$ ，适当地使用剪枝和滚动数组可以大幅减小常数。
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
#define MaxM 65
#define MaxS 33000
using namespace std;
const int mod=998244353;
int f[MaxS],g[MaxS],out[MaxS];
struct Line{int u,v,w;}l[MaxM];
bool cmp(const Line &A,const Line &B)
{return A.w>B.w;}
int n,m,pw2[MaxM];
int main()
{
scanf("%d%d",&n,&m);
pw2[0]=1;
for (int i=1;i<=m;i++)pw2[i]=(pw2[i-1]<<1)%mod;
for (int i=1;i<=m;i++){
scanf("%d%d%d",&l[i].u,&l[i].v,&l[i].w);
l[i].u--;l[i].v--;
}
sort(l+1,l+m+1,cmp);
int ans=0,lim=1<<n;
for (int i=0;i<n;i++)f[1<<i]=g[1<<i]=1;
for (int k=1;k<=m;k++){
int u=l[k].u,v=l[k].v,buf=0;
for (int S=lim-1;S;S--)
if ((S>>u&1)&&(S>>v&1)){
int S2=S^(1<<u)^(1<<v),buf2=f[S]-g[S];
f[S]=(f[S]<<1)%mod;
for (int A2=S2;;A2=(A2-1)&S2){
int A=A2|(1<<u),B=S^A;
buf2=(buf2+1ll*(f[A]-g[A])*(f[B]-g[B]))%mod;
f[S]=(f[S]+1ll*f[A]*f[B])%mod;
g[S]=(g[S]+1ll*g[A]*g[B])%mod;
if (!A2)break;
}buf=(buf+1ll*pw2[out[S]]*buf2)%mod;
}else if (!(S>>u&1)&&!(S>>v&1))out[S]++;
ans=(ans+1ll*l[k].w*(pw2[k-1]-buf)%mod*pw2[m-k])%mod;
}
int inv2=(mod+1)/2;
for (int i=1;i<=m;i++)ans=1ll*ans*inv2%mod;
printf("%d",(ans+mod)%mod);
return 0;
}
```