登录
← 返回首页 | 代码片段 › 3 图论 › 3.2 最小生成树 › 最小生成树 / 搜索
JSON MD

3.2 最小生成树

严格次小生成树 add
78 行
CPP JSON
【严格次小生成树】 最小生成树(MST)算法模板,使用 Kruskal/Prim 算法。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y,Re z) — 加法更新 void dfs(Re x,Re fa) — 深度优先搜索遍历 int lca(Re x,Re y) — 查询最近公共祖先 int ask_max(Re x,Re Ant,Re w) — 核心算法函数 int find(Re x) — 查找(并查集寻根/二分查找) void kruscal(无参数) — 计算函数 核心结构体:QAQ, QWQ, LCA 关键配置: N=5e5+3,M=5e5+3,logN=19,inf=2e9 复杂度:O(E log E)(Kruskal),O(V² / E log V)(Prim) 适用场景:连通图的最小代价连接、瓶颈路问题
C++ 77 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=5e5+3,M=5e5+3,logN=19,inf=2e9;
int T,n,m,o,root,fa[N],head[N],Tree[M],M1[N][23],M2[N][23];LL MinTree;
struct QAQ{int w,to,next;}a[M<<1];
struct QWQ{int x,y,w;inline bool operator<(QWQ O)const{return w<O.w;}}A[M];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
struct LCA{
	int deep[N],ant[N][23];
	inline void dfs(Re x,Re fa){
		deep[x]=deep[fa]+1,ant[x][0]=fa;
		for(Re i=1;(1<<i)<=deep[x];++i){
			ant[x][i]=ant[ant[x][i-1]][i-1];
			M1[x][i]=max(M1[x][i-1],M1[ant[x][i-1]][i-1]);
			M2[x][i]=max(M2[x][i-1],M2[ant[x][i-1]][i-1]);
			if(M1[x][i-1]!=M1[ant[x][i-1]][i-1])
				M2[x][i]=max(M2[x][i],min(M1[x][i-1],M1[ant[x][i-1]][i-1]));
		}
		for(Re i=head[x],to;i;i=a[i].next)
			if((to=a[i].to)!=fa)M1[to][0]=a[i].w,M2[to][0]=-inf,dfs(to,x);
	}
	inline int lca(Re x,Re y){
		if(deep[x]>deep[y])swap(x,y);
		for(Re i=logN;i>=0;--i)if(deep[x]<=deep[y]-(1<<i))y=ant[y][i];
		if(x==y)return y;
		for(Re i=logN;i>=0;--i)
			if(ant[x][i]^ant[y][i])x=ant[x][i],y=ant[y][i];
		return ant[x][0];
	}
	inline int ask_max(Re x,Re Ant,Re w){
		Re ans=-inf;
		for(Re i=logN;i>=0;--i)
			if(deep[ant[x][i]]>=deep[Ant]){
				if(w!=M1[x][i])ans=max(ans,M1[x][i]);
				else ans=max(ans,M2[x][i]);
				x=ant[x][i];
			}
		return ans;
	}
}T1;
inline int find(Re x){return x==fa[x]?x:fa[x]=find(fa[x]);}
inline void kruscal(){
	sort(A+1,A+m+1);
	for(Re i=1;i<=n;++i)fa[i]=i;
	for(Re i=1;i<=m;++i){
		Re x=A[i].x,y=A[i].y,w=A[i].w;
		if(find(x)!=find(y)){
			MinTree+=w,Tree[i]=1;
			add(x,y,w),add(y,x,w);
			fa[find(x)]=find(y);
		}
	}
}
int main(){
	in(n),in(m),root=1;
	for(Re i=1;i<=m;++i)in(A[i].x),in(A[i].y),in(A[i].w);
	kruscal();
	M1[root][0]=0,M2[root][0]=-inf,T1.dfs(root,0);
	LL ans=1e17;
	for(Re i=1;i<=m;++i)
		if(!Tree[i]){
			Re x=A[i].x,y=A[i].y,w=A[i].w;
			Re lca=T1.lca(x,y);
			ans=min(ans,MinTree+w-max(T1.ask_max(x,lca,w),T1.ask_max(y,lca,w)));
		}
	printf("%lld",ans);
}
曼哈顿距离最小生成树 Object Clustering
63 行
CPP JSON
【曼哈顿距离最小生成树(Object Clustering)】 最小生成树(MST)算法模板,使用 Kruskal/Prim 算法。 核心函数: void in(Re &x) — 核心算法函数 LL Abs(LL a) — 核心算法函数 LL Dis(Re x,Re y) — 核心算法函数 void CL(无参数) — 核心算法函数 void add(Re x,Re v,Re ID) — 加法更新 LL ask(Re x) — 核心算法函数 LL find_(Re x) — 查找(并查集寻根/二分查找) LL find(Re x) — 查找(并查集寻根/二分查找) 核心结构体:QAQ, Point, BIT 复杂度:O(E log E)(Kruskal),O(V² / E log V)(Prim) 说明:freopen("123.txt","r",stdin); 适用场景:连通图的最小代价连接、瓶颈路问题
C++ 62 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register LL
using namespace std;
const LL N=1e4+3;
inline void in(Re &x){
	int f=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=f?-x:x;
}
LL n,m,x,y,t,K,Ans,b[N];
struct QAQ{LL x,y,v;inline bool operator<(const QAQ &O)const{return v<O.v;}}a[N<<3];
struct Point{LL x,y,id;inline bool operator<(const Point &O)const{return x!=O.x?x<O.x:y<O.y;}}P[N];
inline LL Abs(LL a){return a<0?-a:a;}
inline LL Dis(Re x,Re y){return Abs(P[x].x-P[y].x)+Abs(P[x].y-P[y].y);}
struct BIT{
	LL n,C[N],id[N];
	inline void CL(){memset(C,127,sizeof(C));}
	inline void add(Re x,Re v,Re ID){while(x){if(v<C[x])C[x]=v,id[x]=ID;x-=x&-x;}}
	inline LL ask(Re x){Re Min=1e18,ID=0;while(x<=n){if(C[x]<Min)Min=C[x],ID=id[x];x+=x&-x;}return ID;}
}TR;
inline LL find_(Re x){
	Re l=1,r=t;
	while(l<r){
		Re mid=(l+r+1)>>1;
		if(b[mid]<=x)l=mid;
		else r=mid-1;
	}
	return l;
}
LL fa[N];
inline LL find(Re x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline void kruscal(){
	for(Re O=1;O<=4;++O){
		if(!(O&1))for(Re i=1;i<=n;++i)swap(P[i].x,P[i].y);
		else if(O==3)for(Re i=1;i<=n;++i)P[i].x*=-1;
		sort(P+1,P+n+1);
		for(Re i=1;i<=n;++i)b[i]=P[i].y-P[i].x;
		sort(b+1,b+n+1),t=unique(b+1,b+n+1)-b-1;
		TR.n=t,TR.CL();
		for(Re i=n;i>=1;--i){
			Re I=find_(P[i].y-P[i].x),j=TR.ask(I);
			if(j)a[++m]=(QAQ){P[i].id,P[j].id,Dis(i,j)};
			TR.add(I,P[i].x+P[i].y,i);
		}
	}
	sort(a+1,a+m+1);
	for(Re i=1;i<=n;++i)fa[i]=i;
	for(Re i=1,t=0;i<=m&&t<n-1;++i)if((x=find(a[i].x))!=(y=find(a[i].y))){
		fa[x]=y,Ans+=a[i].v;
		if(++t==K)printf("%lld\n",a[i].v);
	}
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(K),K=n-1-K+1;
	for(Re i=1;i<=n;++i)in(P[i].x),in(P[i].y),P[i].id=i;
	kruscal();
}
最小生成树 Kruscal
26 行
CPP JSON
【最小生成树(Kruscal)】 最小生成树(MST)算法模板,使用 Kruskal/Prim 算法。 核心函数: void in(Re &x) — 核心算法函数 int find(Re x) — 查找(并查集寻根/二分查找) 核心结构体:QAQ 关键配置: N=5003,M=2e5+3 复杂度:O(E log E)(Kruskal),O(V² / E log V)(Prim) 适用场景:连通图的最小代价连接、瓶颈路问题
C++ 25 行 CPP
#include<algorithm>
#include<cstdio>
#define Re register int
using namespace std;
const int N=5003,M=2e5+3;
int n,m,ans,fa[N];
struct QAQ{int x,y,w;inline bool operator<(const QAQ &O)const{return w<O.w;};}A[M];
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
inline int find(Re x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main(){
	in(n),in(m);
	for(Re i=1;i<=n;++i)fa[i]=i;
	for(Re i=1;i<=m;++i)in(A[i].x),in(A[i].y),in(A[i].w);
	sort(A+1,A+m+1);
	for(Re i=1,t=0;i<=m&&t<n-1;++i){
		Re x=find(A[i].x),y=find(A[i].y);
		if(x!=y)++t,ans+=A[i].w,fa[x]=y;
	}
	printf("%d",ans);
}
最小生成树 LCT
88 行
CPP JSON
【最小生成树(LCT)】 最小生成树(MST)算法模板,使用 Kruskal/Prim 算法。 核心函数: void in(Re &x) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 void updata(Re p) — 核心算法函数 void pushdown(Re p) — 下传懒标记 int nort(Re p) — 核心算法函数 int which(Re p) — 核心算法函数 void connect(Re p,Re fa,Re o) — 核心算法函数 void rotate(Re p) — 旋转操作(平衡树) 核心结构体:Link_Cut_Tree, QAQ 关键配置: N=205003 复杂度:O(E log E)(Kruskal),O(V² / E log V)(Prim) 说明:freopen("123.txt","r",stdin); 适用场景:连通图的最小代价连接、瓶颈路问题
C++ 87 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
#define LL long long
using namespace std;
const int N=205003;
int n,m,x,y,z,id,ans,id_O,v[N];
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct Link_Cut_Tree{
	#define pl tr[p].ps[0]
	#define pr tr[p].ps[1]
	#define pf tr[p].fa
	int Q[N];
	struct QAQ{int fa,mx,mxw,tag,ps[2];}tr[N];
	inline void pushup(Re p){
		tr[p].mx=v[p],tr[p].mxw=p;
		if(pl&&tr[pl].mx>tr[p].mx)tr[p].mx=tr[pl].mx,tr[p].mxw=tr[pl].mxw;
		if(pr&&tr[pr].mx>tr[p].mx)tr[p].mx=tr[pr].mx,tr[p].mxw=tr[pr].mxw;
	}
	inline void updata(Re p){swap(pl,pr),tr[p].tag^=1;}
	inline void pushdown(Re p){
		if(tr[p].tag){
			if(pl)updata(pl);
			if(pr)updata(pr);
			tr[p].tag=0;
		}
	}
	inline int nort(Re p){return tr[pf].ps[0]==p||tr[pf].ps[1]==p;}
	inline int which(Re p){return tr[pf].ps[1]==p;}
	inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
	inline void rotate(Re p){
		Re fa=pf,fas=which(p);
		Re pa=tr[fa].fa,pas=which(fa);
		Re x=tr[p].ps[fas^1];
		if(nort(fa))tr[pa].ps[pas]=p;pf=pa;
		connect(x,fa,fas),connect(fa,p,fas^1);
		pushup(fa),pushup(p);
	}
	inline void splay(Re p){
		Re x=p,t=0;Q[++t]=x;
		while(nort(x))Q[++t]=x=tr[x].fa;
		while(t)pushdown(Q[t--]);
		for(Re fa;nort(p);rotate(p))
			if(nort(fa=pf))rotate(which(p)==which(fa)?fa:p);
	}
	inline void access(Re p){
		for(Re son=0;p;son=p,p=pf)
			splay(p),pr=son,pushup(p);
	}
	inline void makeroot(Re p){access(p),splay(p),updata(p);}
	inline int findroot(Re p){
		access(p),splay(p),pushdown(p);
		while(pl)pushdown(p=pl);
		return p;
	}
	inline void split(Re x,Re y){makeroot(x),access(y),splay(y);}
	inline void link(Re x,Re y){makeroot(x);if(findroot(y)!=x)tr[x].fa=y;}
	inline void cut(Re x,Re y){
		makeroot(x);
		if(findroot(y)==x&&tr[x].fa==y&&!tr[x].ps[1])
			tr[x].fa=tr[y].ps[0]=0,pushup(y);
	}
	inline int judge(Re x,Re y){makeroot(x);return findroot(y)==x;}
	inline void sakura(Re x,Re y,Re z,Re id){
		if(!judge(x,y))link(x,id),link(id,y),ans+=z;
		else{
			split(x,y);Re mx=tr[y].mx,mxw=tr[y].mxw;
			if(z<mx){
				ans+=z-mx,splay(mxw);
				tr[tr[mxw].ps[0]].fa=tr[tr[mxw].ps[1]].fa=0;
				link(x,id),link(id,y);
			}
		}
	}
}LCT;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m);
	while(m--)in(x),in(y),in(z),v[id=++id_O+n]=z,LCT.sakura(x,y,z,id);
	printf("%d\n",ans);
}
最小生成树 Prim n^2
31 行
CPP JSON
【最小生成树(Prim n^2)】 最小生成树(MST)算法模板,使用 Kruskal/Prim 算法。 核心函数: void in(Re &x) — 核心算法函数 void Prim(无参数) — Prim最小生成树 关键配置: N=5003,M=2e5+3,inf=2e9 复杂度:O(E log E)(Kruskal),O(V² / E log V)(Prim) 适用场景:连通图的最小代价连接、瓶颈路问题
C++ 30 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
using namespace std;
const int N=5003,M=2e5+3,inf=2e9;
int n,x,y,z,T,ans,pan[N],dis[N],a[N][N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void Prim(){
	for(Re i=0;i<=n;++i)dis[i]=inf;
	Re t=0;dis[1]=0;
	for(Re i=1;i<=n&&t<n;++i){
		Re w=0;
		for(Re j=1;j<=n;++j)if(!pan[j]&&dis[j]<dis[w])w=j;
		pan[w]=1,ans+=dis[w],++t;
		for(Re j=1;j<=n;++j)if(!pan[j])dis[j]=min(dis[j],a[w][j]);
	}
}
int main(){
	in(n),in(T);
	memset(a,127,sizeof(a));
	while(T--)in(x),in(y),in(z),a[x][y]=a[y][x]=min(a[x][y],z);
	Prim();
	printf("%d\n",ans);
}
最小生成树 Prim
35 行
CPP JSON
【最小生成树(Prim)】 最小生成树(MST)算法模板,使用 Kruskal/Prim 算法。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y,Re z) — 加法更新 void Prim(无参数) — Prim最小生成树 核心结构体:QAQ, QWQ 关键配置: N=5003,M=2e5+3,inf=2e9 复杂度:O(E log E)(Kruskal),O(V² / E log V)(Prim) 适用场景:连通图的最小代价连接、瓶颈路问题
C++ 34 行 CPP
#include<algorithm>
#include<cstdio>
#include<queue>
#define Re register int
using namespace std;
const int N=5003,M=2e5+3,inf=2e9;
int x,y,z,n,m,o,ans,pan[N],dis[N],head[N];
struct QAQ{int w,to,next;}a[M<<1];
struct QWQ{int x,d;inline bool operator<(QWQ o)const{return d>o.d;};};
priority_queue<QWQ>Q;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void Prim(){
	for(Re i=0;i<=n;++i)pan[i]=0,dis[i]=inf;
	Re t=0;Q.push((QWQ){1,dis[1]=0});
	while(!Q.empty()&t<n){
		Re x=Q.top().x;Q.pop();
		if(pan[x])continue;
		pan[x]=1,++t,ans+=dis[x];
		for(Re i=head[x],to;i;i=a[i].next)
			if(dis[to=a[i].to]>a[i].w)Q.push((QWQ){to,dis[to]=a[i].w});
	}
}
int main(){
	in(n),in(m);
	while(m--)in(x),in(y),in(z),add(x,y,z),add(y,x,z);
	Prim();
	printf("%d",ans);
}
已复制