　　　　　　　　次小生成树

导入：次小生成树是在最小生成树的基础上求得的，是noip提高组常考点之一，

　　　有着较高的灵活性。

算法简介：

　　学习次小生成树之前你得先弄明白最小生成树，假设有一n个点m条边的无向

　　图，求次小生成树基本步骤如下：

　　1.求出最小生成树，并将所有树边建树。

　　2.依次枚举非树边，并将其加入树上，形成一个环。

　　3.在环上找到一边满足：除非树边外最大（如果要求求严格次小生成树还需

　　满足边权小于新加入的非树边）。

　　4.删去该边，求出树的边权合。

　　5.重复2.3.4。

　　正确性证明：

　　　　将最小生成树的边权和记为S，非树边边权记为V，除树边外最大边权记为U，此时

　　　　生成树的边权为S-U+V，假设存在一边边权记为Q使得S-Q+V<S-U+V则必须满足

　　　　Q>U与假设不符，即选择U为最优方案。

　　　　这个算法乍一看，求最小生成树O（mlogm）枚举非树边O(m)找到满足条

　　件的边O(m)总的时间复杂度为O(mlogm+m*m)只适用于（m<5000)接下来我们

　　对算法进行优化，由于OI比赛中一般考察严格次小生成树，我们以严格次小为

　　例来讨论。

　　　　由于最小生成树求法我们基于已有最优算法，不再考虑优化，O(m)枚举显

　　然无法优化因此我们只考虑寻找可行边的优化。假设我们现在有一张图求出的

　　最小生成树如下

　　下面我们加入一条边（12,15）

　　　　此时形成一个环我们要在这个环上寻找可行边，不妨将其以最近公共祖先

　　为界分为两部分，变成两条链，那问题便成为了在两条链上求最大值和次大值

　　（记录次大值防止最大值与非树边边权一样时求出的不是严格次小生成树）

　　　　那么我们可以使用倍增进行求解，由于最近公共祖先也需使用倍增求解，

　　我们可以在求最近公共祖先的时候同时求解出最大值次大值。复杂度从O(m)降

　　为O(logm)

　　ac代码：

#include<bits/stdc++.h>
#define N 500010
#define inf 0x3f3f3f3f3f3f3f3f

using namespace std;

struct node
{
	int f,t,v;
	bool friend operator <(const node a,const node b)
	{
		return a.v<b.v;
	}
}ee[N],dl[N];

int head[N],to[N],net[N],vis[N],cnt;
int f[21][N],v[2][21][N],d[N];
int n,m;
long long ans=inf,sum;
int fa[N];
int num;

void add(int from,int t,int v)
{
	net[++cnt]=head[from];
	to[cnt]=t;
	vis[cnt]=v;
	head[from]=cnt;
}

int found(int x)
{
	if(fa[x]!=x)return fa[x]=found(fa[x]);
	return fa[x];
}

void kul()
{
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		node e=dl[i];
		int fx=found(e.f);
		int fy=found(e.t);
		if(fx!=fy)
		{
			add(e.f,e.t,e.v);
			add(e.t,e.f,e.v);
			fa[fx]=fy;
			sum+=e.v;
		}
		else ee[++num]=e;
	}
}

void LCA(int fa,int x,int vv)
{
	d[x]=d[fa]+1;
	f[0][x]=fa;
	v[0][0][x]=vv;
	for(int i=1;i<=16;i++)
	{
		f[i][x]=f[i-1][f[i-1][x]];
		v[0][i][x]=max(v[0][i-1][x],v[0][i-1][f[i-1][x]]);
		int q[]={v[0][i-1][x],v[0][i-1][f[i-1][x]],v[1][i-1][x],v[1][i-1][f[i-1][x]]};
		sort(q,q+4);
		for(int j=0;j<4;j++)
			if(q[j]!=v[0][i][x])v[1][i][x]=q[j];
	}
	for(int i=head[x];i;i=net[i])
		if(to[i]!=fa)
			LCA(x,to[i],vis[i]);
}

void lca(node e)
{ 
	int q[N];
	int t=0;
	int x=e.f,y=e.t,vi=e.v;
	if(d[x]<d[y])swap(x,y);
	for(int i=16;i>=0;i--)
		if(d[f[i][x]]>=d[y])
			q[++t]=v[0][i][x],q[++t]=v[1][i][x],x=f[i][x];
	if(x!=y)
	{
		for(int i=16;i>=0;i--)
			if(f[i][x]!=f[i][y])
			{
				q[++t]=v[0][i][x],q[++t]=v[0][i][y];
				q[++t]=v[1][i][x],q[++t]=v[1][i][y];
				x=f[i][x],y=f[i][y];
			}
		q[++t]=v[0][0][x];
	}
	sort(q+1,q+t+1);
	int vv;
	for(int i=t;i;i--)
		if(vi!=q[i])
		{
			vv=q[i];
			break;
		}
	ans=min(ans,sum+vi-vv);

}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y,v;
		scanf("%d%d%d",&x,&y,&v);
		dl[i]={x,y,v};
	}
	sort(dl+1,dl+m+1);
	kul();
	LCA(0,1,0);
	for(int i=1;i<=num;i++)
		lca(ee[i]);
	cout<<ans;
	return 0;
}

次小生成树

次小生成树

推荐阅读

　　　　　　　　次小生成树