kruskal重构树

感觉再颓下去可以死家里

算法概述

以下内容最好搭配洛谷日报和oi-wiki食用

理论就不讲了吧。。。逃

讲一下性质：

原图中两个点间所有路径上的边最大权值的最小值=最小生成树上两点简单路径的边最大权值= \(\text{Kruskal}\)重构树上两点 \(\text{LCA}\)的点权。

emm，好像就没了

例题

P1967 [NOIP2013 提高组] 货车运输

纯板子，主要是贴个代码（但这码风是真的丑）

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
int tot,ne[N<<1],to[N<<1],head[N<<1];
int f[N][20],v[N],fa[N],vis[N];
int idx,tin[N],tout[N];
inline void add(int x,int y)
{
	to[++tot]=y,ne[tot]=head[x],head[x]=tot;
}
void dfs(int x)
{
	tin[x]=++idx,vis[x]=1;
	for(int i=0;f[x][i];++i) f[x][i+1]=f[f[x][i]][i];
	for(int y,i=head[x];i;i=ne[i])
	{
		if((y=to[i])==f[x][0]) continue;
		f[y][0]=x,dfs(y);
	}
	tout[x]=++idx;
}
inline int pd(int x,int y){return tin[x]<=tin[y]&&tout[x]>=tout[y];}
inline int lca(int x,int y)
{
	if(pd(x,y)) return x;
	if(pd(y,x)) return y;
	for(int i=19;i>=0;--i)
		if(f[x][i]&&!pd(f[x][i],y)) x=f[x][i];
	return f[x][0];
}
inline int find(int x)
{
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
struct edge
{
	int x,y,z;
	inline bool operator<(const edge &res)const
	{
		return z>res.z;
	}
}ed[N];
inline void Ex_kruskal()
{
	int cnt=n;
	for(int i=1;i<=2*n;++i) fa[i]=i;
	sort(ed+1,ed+m+1);
	for(int i=1;i<=m;++i)
	{
		int x=find(ed[i].x),y=find(ed[i].y);
		if(x!=y)
		{
			fa[x]=fa[y]=++cnt,v[cnt]=ed[i].z;
			add(cnt,x),add(x,cnt);
			add(cnt,y),add(y,cnt);
			if(cnt==2*n-1) break;
		}
	}
	for(int i=cnt;i;--i) if(!vis[i]) dfs(i);
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;++i) cin>>ed[i].x>>ed[i].y>>ed[i].z;
	Ex_kruskal();
	cin>>m;
	int x,y;
	while(m--)
	{
		cin>>x>>y;
		cout<<(find(x)==find(y)?v[lca(x,y)]:-1)<<endl;
	}
}

P4768 [NOI2018] 归程

看到最短路，先考虑 SPFA \(dijkstra\)

然后预处理出源点到每个点的最短路，在上面倍增就行了

代码不放了，主要是没调出来

P4197 Peaks

这道题我们先倍增找到能跳到的最远祖先，然后主席树查第K大即可

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5,INF=1e9;
struct edge
{
	int x,y,z;
	inline bool operator<(const edge &res)const
	{
		return z<res.z;
	}
}ed[N];
int p[N],val[N],vis[N];
int f[N][20],to[N],head[N],ne[N],tot;
int tin[N],tout[N],idx;
int n,m,q,cnt;
int find(int x)
{
	return p[x]==x?x:p[x]=find(p[x]);
}
inline void add(int x,int y)
{
	ne[++tot]=head[x],head[x]=tot,to[tot]=y;
}
void dfs(int x,int fa)
{
	f[x][0]=fa,vis[x]=1,tin[x]=++idx;
	for(int i=0;f[x][i];++i) f[x][i+1]=f[f[x][i]][i];
	for(int i=head[x],y=to[i];i;y=to[i=ne[i]])
		if(y!=fa) dfs(y,x);
	tout[x]=++idx;
}
inline void Ex_kruskal()
{
	cnt=n;
	for(int i=1;i<=n*2;++i) p[i]=i;
	sort(ed+1,ed+m+1);
	for(int i=1;i<=m;++i)
	{
		int x=find(ed[i].x),y=find(ed[i].y);
		if(x==y) continue;
		p[x]=p[y]=++cnt,val[cnt]=ed[i].z;
		add(cnt,x),add(cnt,y);
		add(y,cnt),add(x,cnt);
		if(cnt==2*n-1) break;
	}
	for(int i=1;i<=cnt;++i) if(!vis[i]) dfs(find(i),0);
}
int id[N],nid[N],sz[N];
void dfs1(int x,int fa)
{
	vis[x]=1;
	id[++idx]=x,nid[x]=idx,sz[x]=1;
	for(int i=head[x],y=to[i];i;y=to[i=ne[i]])
		if(y!=fa) dfs1(y,x),sz[x]+=sz[y];
}
int root[N],xb;
struct tree
{
	int lc,rc,v;
}t[N<<4];
void ins(int &k,int p,int l,int r,int x,int v)
{
	t[k=++xb]=t[p];
	t[k].v+=v;
	if(l==r) return;
	int mid=l+r>>1;
	if(x<=mid) ins(t[k].lc,t[p].lc,l,mid,x,v);
	else ins(t[k].rc,t[p].rc,mid+1,r,x,v);
}
inline void pre()
{
	idx=0;
	for(int i=1;i<=cnt;++i) vis[i]=0;
	for(int i=1;i<=cnt;++i) if(!vis[i]) dfs1(find(i),0);
	for(int i=1;i<=cnt;++i)
	{
		if(id[i]<=n) ins(root[i],root[i-1],1,INF,val[id[i]],1);
		else root[i]=root[i-1];
	}
}
inline int find1(int x,int v)
{
	for(int i=19;i>=0;--i)
		if(f[x][i]&&val[f[x][i]]<=v) x=f[x][i];
	return x;
}
int ask(int p,int q,int l,int r,int k)
{
	if(l==r) return l;
	int k1=t[t[p].rc].v-t[t[q].rc].v,mid=l+r>>1;
	if(k1>=k) return ask(t[p].rc,t[q].rc,mid+1,r,k);
	else return ask(t[p].lc,t[q].lc,l,mid,k-k1);
}
inline int query(int x,int v,int k)
{
	int p=find1(x,v);
	return t[root[nid[p]+sz[p]-1]].v-t[root[nid[p]-1]].v<k?-1:ask(root[nid[p]+sz[p]-1],root[nid[p]-1],1,INF,k);
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>q;
	int x,y,z;
	for(int i=1;i<=n;++i) cin>>val[i];
	for(int i=1;i<=m;++i) cin>>ed[i].x>>ed[i].y>>ed[i].z;
	Ex_kruskal();
	pre();
	while(q--)
	{
		cin>>x>>y>>z;
		cout<<query(x,y,z)<<endl;
	}
}

总结

第一篇学习笔记，狗屁不通，请轻喷