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

极值生成树(MST)相关理论,默认以最小生成树为例

比较常用的两种思考方向:

将点划分成两个真子集a和b,在两个点集间连边恰有一条

将某条边加入生成树,形成一个环

一车性质

基本都是用反证法,可以闲着没事过来反复推一推,有益无害,而且基本不难证

性质1:任意真子集划分(a,b),在MST中连接着两个点集的边一定是,这两个点集间边权中最小的

证明:如果不是,替换为这个肯定更优

性质2:MST一定是最小瓶颈生成树

证明:设B为MST,A为最小瓶颈生成树,即$sum(A) \ge sum(B),mx(A)<mx(B)$;那么随便找个划分(a,b)满足$mx(B)$沟通两个点集,则一定在A中也有一条边沟通这两个点集,而且那条边不可能出现在B中(顶部加粗文字)

性质3(重要):MST不唯一,但MST的边权多重集唯一

考虑每次将同权值的所有边一起加入图中这个过程,先把那些两端本来就在同个联通块中的边去掉,那么这次新合并多少个联通块是确定的,即要在其中保留多少条边是确定的,新的连通信息与方案无关,得证

附以前yy的繁琐证明,不感兴趣可跳过

不失一般性地设两个MST(A和B)的边权集合从小到大首次不同的权值a<b,则A中「边权为a的边」至少有一条没有在B中

然后我们将通过归纳证明,我们可以在不破坏两边都是MST的前提下,使得在a前面的都在B中出现

即已知前i-1条边都已经在B中出现,那么$<a_i$的所有边都在B中了,此时在B中加入第i条边,形成的环不可能除自己外都$<a_i$(否则这些边肯定都在A中存在,则A中成环),那么替换掉最大的边(最坏情况下$=a_i$)并不会破坏掉MST,证毕

通过这样的调整,现在在B中加入a,那么环上的边一定不可能都$\le a$,将最大的替换掉会使和变小,故不存在这种情况

小推论:有的题目边权为边的编号之类的排列,这样的图的MST唯一

性质4:图上最小瓶颈路径一定可以在MST上

证明:最小瓶颈路径的的求法很自然的思路是从小到大加边直到连通,发现和MST的过程相同

Kruskal

并查集维护连通性,每次取最小的,连接两个森林的一条边,$O(mlogm)$

kruskal重构树的简洁教程,经典例题:[ONTAK2010]Peaks加强版,大概就是利用重构树堆的性质找点,然后利用结构性质查询信息

Prim

维护一个树,每次取「加入这棵树的代价」最小的那个点加入,$O(n^2)$

Boruvka

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

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

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

「一类线性二分」

经典必做题

极值生成基环树森林:bzoj4883 [Lydsy1705月赛]棋盘上的守卫jsc2019-qual E Card Collector

请先思考后再展开

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

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

code

期望最小生成树: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内;加强版:没有上面的特殊限制,$n \le 100,m \le C_n^2$

请先思考后再展开

原题:

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

加强版:

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

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