「OI之路」04图论-7生成树

极值生成树(MST)相关
计数的话见【数学-快乐计数】一章

最小(大)生成树

性质1:
对于点集中的一个真子集a,其补集b,连接a和b的边中,边权最小的为t,则必定在最小生成树中出现
证明:
设有某种最小生成树并不包含t,因为连通,总有一条边连接集合a和b,替换为t后显然会不差

性质2:
设f(生成树)=最大边权,则最小生成树一定有最小的f
证明:
设某个非最小生成树有更小的f,则总有一条边,和最小生成树的f那条边的连通性贡献相同(连接a和b点集)

这个称之为最小瓶颈生成树,不过最小瓶颈生成树可能不是最小生成树

性质3:
相同权值的边,对mst的贡献总是相同的,也就是mst的边权序列总是相同的(显然边权序列相同意味着边权和相同)
证明:
设两个mst,边权序列(升序)最前的不同位置,设a中的e更小
将e插入到b,形成了一个环,其中一定存在一条边 「权值>e」
(否则,因为e是第一个不同,更小意味着两棵树都有,则在a中形成环)
显然是可以替换掉的,违背「都是mst」
推论:「没有相同边权」的无向图,最小生成树唯一

推论2:对于权值val用了k次,只用小于val的生成最小森林后,任意一种val的边中选k条且没成环的方案,形成连通信息相同

性质4:
连通图上,a到b「最长边最小」的路径,总是在kruskal生成的mst上
证明:
感受一下,显然很对
首先,每个mst的贡献一定是一样的,这个很好推
然后这个知道以后,反证一个非mst,会使当前mst变小,用类似前面的方法即可

Kruskal

并查集维护连通性,每次取最小的,连接两个森林的一条边
时间复杂度$O(m log m)$

Prim

维护一个树,开始只有一个节点1
加入n-1次,每次选择「加入这棵树的代价」最小的那个点
时间复杂度如果直接暴力是 $O(n^2)$ 的,如果加入二叉堆可以变成 $O(m log_2 n)$
如果logm和logn相差不大的话,写kruskal会比较好
所以说prim只适用于稠密图

Boruvka

并查集维护连通块,然后不断进行下面操作:
枚举每条边,得到距离每个连通块最近的连通块,然后合并起来
这样连通块大小在i次后至少为 $2^i$ ,故只执行log次

这东西在解决「完全图,边权为位运算的极值mst」问题时非常方便,详见这里

最小瓶颈生成树的线性求法

见oi之路的「一类线性二分」

极值生成基环树森林

bzoj4883 [Lydsy1705月赛]棋盘上的守卫jsc2019-qual E Card Collector:code

实话说这两道都是水题,你必须熟练地想到行、列建点格子建边,然后每条边选择一段挂上去而每个节点只能挂一条边,是个经典的基环树模型。

那么现在要生成基环树森林,考虑Kruskal,尝试排序后加入,如果连接一树一基环也能合并,如果是同树内就转成基环树,注意两棵基环树不能合并;考虑正确性,回忆kruskal的证明,你发现出现不同的地方就是一棵树选择转成基环树还是和另一棵基环树合并,考虑到总是在最差的那条边连接,按照优先级处理是没有问题的,然后这个改造和原本生成树也没有冲突,$O(mlogm)$

期望最小生成树

准确的说是,每条边有概率出现,对每个连通块的最小生成树求和,问和的期望;51nod1943 连通期望

感觉std的做法稍复杂?分享一下我的做法,考虑到是最小生成树,从小到大处理每条边,考虑每条边的贡献,那么就是考虑两个集合$A和B(x \in A,y \in B)$,因为这条边的出现才连通的概率,然后乘上这条边的长度

设$f(S)$表示这个点集考虑了前面的边后依然是保持目前连通块的概率,那么每次处理完一条边需要把那些仅一个端点在里面的集合乘上这条边不出现的概率,否则连通性会不同。但注意到我们合并A和B集合的时候,两个集合中间的边的概率影响会被乘两次,需要搞回来,可以记录一个in表示集合内的已出现边的失败概率乘积,则$T \to S \setminus T=\frac{in(S)}{in(T)in(S \setminus T)}$,维护这个是$O(m2^n)$

那么对于每次转移,$f2(S)为新的f(S),f2(A \cup B)=p*\sum_A f(A)*f(B)*\frac{in(A \cup B)}{in(A)in(B)}$

你会发现这个式子可以用子集卷积优化,然而并没有什么卵用qaq

$O(3^{n-2}m)$,应该大家做法是一样的,没卡常不知为啥登顶了

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
struct Edge{int x,y,c;double p;}e[N];bool cmp(Edge a,Edge b){return a.c<b.c;}
double f[1<<14],in[1<<14];
void main()
{
int n=qread(),m=qread();
fo(i,1,m) {e[i].x=qread()-1,e[i].y=qread()-1,e[i].c=qread();scanf("%lf",&e[i].p);e[i].p=1-e[i].p;}sort(e+1,e+m+1,cmp);

fo(i,0,n-1) f[bin(i)]=1;
fo(i,0,bin(n)-1) in[i]=1;
double ans=0;
fo(k,1,m)
{
int x=e[k].x,y=e[k].y;
fd(S,bin(n)-1,1)
{
f[S]*=((S&bin(x))>0)+((S&bin(y))>0)-1==0?1-e[k].p:1 ;
if(S&bin(x) and S&bin(y))
{
int mask=S^bin(x)^bin(y);
double sum=f[bin(x)]*in[bin(x)]*f[S^bin(x)]*in[S^bin(x)];
for(int T=mask;T>0;T=(T-1)&mask)//if(T&bin(x) and (S^T)&bin(y))
sum+=f[T|bin(x)]*in[T|bin(x)]*f[S^T^bin(x)]*in[S^T^bin(x)];
sum*=e[k].p/in[S];ans+=sum*e[k].c;f[S]+=sum;
}
}
fo(S,0,bin(n)-1) if(S&bin(x) and S&bin(y)) in[S]*=1-e[k].p;
}
printf("%.6lf",ans);
}

最小生成树计数

例题:[JSOI2008]最小生成树计数

原题:相同权值数量在10内;边权序列相同的合法序列一定是mst,根据性质3的推论2,先求出一种mst,模拟kruskal的过程,加入小于val的树边后,选出与mst所用边数相同的合法的k条,这个方案就是对于权值val的答案,把这个乘起来就是结果,$O(m*2^{10})$

加强版(没有上面的特殊限制,$n \le 100,m \le C_n^2$):根据性质,这k条边连通哪些块其实已知,把所有不为val的树边加入,跑一个生成树计数即可,直接做是$O(m*n^3)$的,考虑到$\sum k=n-1,缩点后点数其实为\sum (k+1)^3=O(n^3)$

另一些奇怪的最小生成树

有位老哥做了深入研究:CF125E-MST-Company

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/b399.html
转载请注明出处,谢谢!