首页 > 其他分享 >最小生成树学习笔记

最小生成树学习笔记

时间：2024-09-30 15:33:41浏览次数：7  
标签：val int 边权 最小 笔记 生成 fa ans mx

最小生成树

证明

最小生成树构成的过程实际上是做 \(n-1\) 次操作，每一次合并一个点集，直到图中只剩下一个集合为止 。

要达到的就是让每一次合并的代价之和最小。

那么我们实际上可以贪心地选择边权最小的并且能够合并集合的边（Kruskal算法），这个算法的正确性简单来说可以用反证法来证明，假设我们并没有按照 Kruskal 的流程来选择边，那么显而易见的是，每一次的合并操作一定存在一条边与之对应，而没有遵循 Kruskal 的结果是：至少存在一次操作，我们可以用一条权值更小的边来替代这一次操作所选的边，使得答案变得更优，所以正确性就这样不太严格地得到了证明。

Code

#include<bits/stdc++.h>
#define R register
using namespace std;
template<typename T>inline void re(T &x)
{
	x=0;int f=1;char c=getchar();
	while(!isdigit(c))
	{
		if(c=='-')f=-1;
		c=getchar();
	}
	while(isdigit(c))
	{
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	x*=f;
}
template<typename T>inline void wr(T x)
{
	if(x<0)putchar('-'),x=-x; 
	if(x>9)wr(x/10);
	putchar(x%10^48); 
}
struct Edge
{
	int u,v,w;
}E[1000000];
bool cmp(Edge a,Edge b){return a.w<b.w;}
int fa[100000],n,m,u,v,w;
inline int get(int x){return fa[x]==x?x:fa[x]=get(fa[x]);}
inline void pre()
{
	re(n),re(m);
	for(R int i=1;i<=m;++i)
		re(E[i].u),re(E[i].v),re(E[i].w);
	sort(E+1,E+m+1,cmp);
	for(register int i=1;i<=n;i++)fa[i]=i;
}
inline void solve()
{
	int cnt=0,ans=0;
	for(int i=1;i<=m;i++)
	{
		int fx=get(E[i].u),fy=get(E[i].v);
		if(fx==fy)continue;
		ans+=E[i].w;
		fa[fx]=fy;
		cnt++; 
	}
	if(cnt!=n-1){puts("orz");return;}
	wr(ans);
}
int main()
{
	pre();
	solve();
	return 0;
 }

拓展 ：次小生成树

描述

顾名思义就是除开最小生成树，其它所有生成树中最小的那一个。

思路

我们先把最小生成树跑出来，容易想到这两棵树实际上长得没有太大的差别，我们只需要考虑如何加入一条边，删除一条边，使得原来的 MST 变成我们要求的 Second-MST 。

那么很好想到的一种方法就是枚举所有不在 MST 中的边，记其端点为 \(u,v\) ，由树的性质可以推知，加入这条边一定就会引入一个环，此时我们在这个环上再删除一条不同的边，就可得到一个新的生成树，要尽量让这个生成树的总权值小，我们很明显就是要删除最大的那一条边。

所以我们的任务就变成了：枚举每一条不在 MST 中的边，查询 \(u\) 到 \(v\) 路径上的边权最大值，用 \(val_{MST}-query(u,v)+E[i].w\) 来更新答案，然后发现好像过不了样例。

实际上就是在 “严格” 这个地方出了问题，也就说我们最后得到的答案必须大于原来的 MST 值，言下之意即：拆环的时候不能拆掉和枚举到的边边权相同的边。那么我们就需要同时维护一个路径次大值来防止这种情况，具体转移是这样的（这里用的是倍增）：

			mx[i][j][1]=max(mx[i][j-1][1],mx[fa[i][j-1]][j-1][1]);//max1
			if(mx[i][j-1][1]!=mx[fa[i][j-1]][j-1][1])mx[i][j][2]=min(mx[fa[i][j-1]][j-1][1],mx[i][j-1][1]);
			else mx[i][j][2]=max(mx[i][j-1][2],mx[fa[i][j-1]][j-1][2]);//max2

如果说是 非严格次小生成树的话，那直接只用维护一个路径最大值就可以了，

细节

1.跑mst和进行dfs要分开建图

2.答案要开longlong

3.倍增的时候和求lca的过程不太一样，要注意边界条件

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
struct Edge
{
	int u,v,w,nex;
}E[N],e[N];
bool cmp(Edge a,Edge b)
{
	return a.w<b.w;
}
int tote,head[N];
inline void add(int u,int v,int w)
{
	E[++tote].v=v,E[tote].nex=head[u],E[tote].w=w;
	head[u]=tote;
}
template<typename T>inline void re(T &x)
{
	x=0;
	int f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	x*=f;
}
int n,m;
int dep[N],fa[N][25],mx[N][25][3];
int tag[N];
inline void dfs(int x)
{
	for(int i=head[x];i;i=E[i].nex)
	{
		int v=E[i].v; 
		if(v==fa[x][0])continue;
		dep[v]=dep[x]+1,fa[v][0]=x;
		mx[v][0][1]=E[i].w,mx[v][0][2]=-(1e9+1);
		dfs(v);
	}
}
inline int lca(int x,int y)
{
	if(dep[x]<dep[y])swap(x,y);
	for(register int i=20;i>=0;--i)
		if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
	if(x==y)return x;
	for(register int i=20;i>=0;--i)
	{
		if(fa[x][i]!=fa[y][i])
			x=fa[x][i],y=fa[y][i];
	}
	return fa[x][0];
}
inline int q(int val,int x,int y)
{
	int Lca=lca(x,y);
	int ans=-(1e9+7);
	for(register int i=20;i>=0;--i)
	{
		if(fa[x][i]!=Lca&&dep[fa[x][i]]>dep[Lca])
		{
			if(mx[x][i][1]!=val)ans=max(ans,mx[x][i][1]);
			else ans=max(ans,mx[x][i][2]);
			x=fa[x][i]; 
		}
	}
	if(x!=Lca&&mx[x][0][1]!=val)ans=max(ans,mx[x][0][1]);
	for(register int i=20;i>=0;--i)
	{
		if(fa[y][i]!=Lca&&dep[fa[y][i]]>dep[Lca])
		{
			if(mx[y][i][1]!=val)ans=max(ans,mx[y][i][1]);
			else ans=max(ans,mx[y][i][2]);
			y=fa[y][i]; 
		}
	}
	if(y!=Lca&&mx[y][0][1]!=val)ans=max(ans,mx[y][0][1]);
	return ans;
}
int f[N];
inline int get(int x){return x==f[x]?x:f[x]=get(f[x]);}
long long mst;
inline void Kruskal()
{
	sort(e+1,e+m+1,cmp);
	for(register int i=1;i<=m;i++)
	{
		int fx=get(e[i].u),fy=get(e[i].v);
		if(fx==fy)continue;
		mst+=e[i].w;
		f[fx]=fy;
		tag[i]=1;
	}
} 
inline void pre()
{
	re(n),re(m);
	int u,v,w;
	for(register int i=1;i<=m;++i)
		re(e[i].u),re(e[i].v),re(e[i].w);
	for(register int i=1;i<=n;++i)f[i]=i;
	Kruskal();
	for(register int i=1;i<=m;++i)
	{
		if(!tag[i])continue;
		add(e[i].u,e[i].v,e[i].w);	
		add(e[i].v,e[i].u,e[i].w);	
	}	
	dep[1]=1;
	dfs(1);
	for(int j=1;j<=20;++j)
		for(int i=1;i<=n;++i)
		{
			fa[i][j]=fa[fa[i][j-1]][j-1];
			mx[i][j][1]=max(mx[i][j-1][1],mx[fa[i][j-1]][j-1][1]);//max1
			if(mx[i][j-1][1]!=mx[fa[i][j-1]][j-1][1])mx[i][j][2]=min(mx[fa[i][j-1]][j-1][1],mx[i][j-1][1]);
			else mx[i][j][2]=max(mx[i][j-1][2],mx[fa[i][j-1]][j-1][2]);//max2
		}
}
inline void solve()
{
	long long ans=1e18+1;
//	cout<<mst<<endl;
	for(register int i=1;i<=m;i++)
	{
		if(tag[i])continue;
		int u=e[i].u,v=e[i].v;
		ans=min(ans,mst-q(e[i].w,u,v)+e[i].w);
	}
	cout<<ans;
}
int main()
{
	pre();
	solve();
	return 0;
}
/*
4 4
1 2 1
2 3 2
3 4 1
2 4 2
*/

类题延伸

CF1184E1

题意

一条边的边权待定，如果其在 MST 中，那么它最大的可能边权是多少。

分析

思考1

这道题有很多思考方向，首先发现这个边权和被选在 MST 中一定是具有单调性的，所以可以二分加上一个 Kruskal，复杂度是 \(O(n\log n\log val_m)\)。

从二分的角度来思考，这个边权大到什么程度我们才不会选这条边？记这条边为 \((u,v)\) 的话，也就是有一条能够链接 \(u\) 和 \(v\) 所在集合，而且边权更小的边出现的时候，那么实际上我们要求的最大答案就是这个边权，容易用反证法证明。

思考2

那么从次小生成树考虑呢？

我们先刨去这条边跑一个 MST，假设这条边初值为 \(INF\) ，我们不断降低他的边权直到它能够被加入 MST 中。

这不就是我们找环上路径最大值的过程吗？甚至不不用维护次大值，因为这不要求 “严格”。

思考3

实际上我们会发现，这两种算法最后找到的那条边一定是同一条边。

在mst上面，任意 \(u,v\) 之间的路径是唯一的，按照kruskal算法选出的用来连接 \(u,v\) 的边，一定是 \(u,v\) 路径上的最大值，因为我们是将边权排序后再进行选择的。

总结

关于次小生成树的求法，实际上就是一个维护并查询路径上最大/次大值的过程，可以用LCT来实现，也可以使用倍增，两者的细节不同。

还可以出这样一道题：

一条边 \(i\) 的边权待定，求一个最大的确切范围 \([val_l,val_r]\) ，使得当 \(w_i\in [val_l,val_r]\) 的时候， \(i\) 在这张图的严格次小生成树中（一定有解）。

这就要求我们同上地求出次小生成树 \(SecMST\) 之后，再对待定边加入后构成的环上最大边权值进行查询，记其为 \(Max\) ，那么最后的答案就会是 \([Max+1,Max+(SecMST-MST)]\)

拓展：Kruskal重构树

鸽了

标签：val,int,边权,最小,笔记,生成,fa,ans,mx
From： https://www.cnblogs.com/Hanggoash/p/18441953

相关文章

  • 最大公约数与最小公倍数
    设\(a_1,a_2\)是两个整数，如果\(d|a_1,\d|a_2\)，那么\(d\)就称为\(a_1\)和\(a_2\)的公约数，其中最大的称为\(a_1\)和\(a_2\)的最大公约数，记作\((a_1,a_2)\)。一般地，可以类似地定义\(k\)个整数\(a_1,a_2,\cdots,a_k\)的公约数和最大公约数，后者记作\((a_1,\cdots,......
  • prometheus学习笔记之Grafana 常用操作
    一、Panel设置1.单位设置2.Panel名称修改3.曲线别名修改前修改后 4.曲线排序 5.曲线复制6.曲线静默 7.Panel复制当前dashboard中复制跨dashboard或folder在其他dashboard中操作8.设置告警线设置告警条件其他按提示填写如果触发告警规则则......
  • 卓越网络安全教程笔记-四-
    卓越网络安全教程笔记（四）P64：11.4-【Metasploit渗透】Metasploit基本使用方法-2-一个小小小白帽-BV1Sy4y1D7qv好接下来我们来看另外一个比较重要的命令，也是我们会经常会用到的一个命令啊，模块相关的命令，柚子的使用方法啊，柚子那么英文翻译过来呢是使用的意思哎，主要通过这个命令......
  • 除氟剂在锂电池回收处理过程中的应用（学习笔记）
    除氟剂在锂电池回收处理过程中的应用是至关重要的，主要目的是去除回收废液中的氟离子，以保护后续处理设备、提高回收金属的品质，并减少对环境的污染。以下是除氟剂在锂电池回收处理过程中的详细应用：一、应用背景在锂电池的回收处理过程中，废旧电池经过拆解、放电、破碎、浸出等......
  • 阳极氧化与废酸处理（学习笔记）
    一、阳极氧化概述阳极氧化（AnodicOxidation）是一种金属或合金的电化学氧化过程。在阳极氧化过程中，金属或合金（如铝及其合金）在相应的电解液（如硫酸、铬酸、草酸等）中，作为阳极，在特定条件和外加电流的作用下，表面形成一层氧化膜。这层氧化膜具有保护性、装饰性以及其他功能特性，如提高......
  • 光伏含氟废水的深度除氟（学习笔记）
    光伏废水中的氟深度除氟是一个复杂但重要的过程，以确保废水在排放前达到环保标准。以下是一些常用的深度除氟方法：一、化学沉淀法化学沉淀法是通过向含氟废水中投加化学试剂，使其与废水中的氟生成氟化物沉淀，然后通过过滤或自然沉降等方法使沉淀物与水分离，达到除氟的目的。这种......
  • 郁金香游戏辅助教程笔记-七-
    郁金香游戏辅助教程笔记（七）P200：217-游戏多开补丁编写_old-教到你会-BV1DS4y1n7qF大家好，我是郁金香老师，那么上一节课呢我们简单的探讨了，那以下这个游戏多开的另外的一种原理，那么这节课呢我们通过上上一节课分析的数据。然后呢来编写相应的代码，那么首先我们打开vs2010。......
  • 郁金香游戏辅助教程笔记-九-
    郁金香游戏辅助教程笔记（九）P55：066-NPC菜单选择CALL-教到你会-BV1DS4y1n7qF大家好，我是郁金香老师，那么在上一节课呢，我们分析了打开npc菜单的功能，那么这节课呢我们主要来分析一下呃，npc菜单选择的一个功能，我们说的肾的函数进行一个下段，然后回溯。当然我们今天这个游戏呢它是用的......
  • 郁金香游戏辅助教程笔记-二-
    郁金香游戏辅助教程笔记（二）P114：125-穿墙功能分析-关键代码-教到你会-BV1DS4y1n7qF大家好，我是郁金香老师，那么这节课呢我们接着上一节课的代码，来继续分析一下有关穿墙的这部分功能，那么上一节课呢我们讲到的是呃，我们已经分析到了一个比较关键的位置啊，也就是这个地方我们把它复......
  • 郁金香游戏辅助教程笔记-八-
    郁金香游戏辅助教程笔记（八）P4：015-DbgPrintMine与变参函数-教到你会-BV1DS4y1n7qF大家好，我是郁金香老师，qq1533057，欢迎大家参加郁金香技术编程和距离，那么这节课呢我们一起来写一个debug啊，矿井m用这个函数来来替代我们的alt固体debug尺寸。因为这个alt库体debug尺寸呢它使用起......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99