lp4768 NOI2018 归程

克鲁斯卡尔重构树模板题。
我们发现,这一题可以拆成两个步骤。第一个步骤,是找到所有u可以通过共享单车达到的点;第二个步骤,是找到这些点中到原点最小的点的距离。
我们容易发现,第一个步骤和长度无关,第二个步骤和海拔无关。
首先考虑第一个步骤。
我们建出一棵克鲁斯卡尔重构树——克鲁斯卡尔重构树是这样的一个数据结构:当你使用克鲁斯卡尔算法建最小/最大生成树的时候,每一次合并,你新建一个节点p,这个点的点权是这一次合并通过的边的边权,然后将即将合并的两个点的根节点合并到p下。这样我们构造出了一棵二叉树,其中所有叶子节点是原图上的节点。
克鲁斯卡尔重构树满足一些有意义的性质。
不妨以这题为例,我们构造一棵最大生成树,那么两点之间的lca的点权就是这两个点之间路径中边权最大的值。换句话说,从u在d的降水下可以到的节点,就是所有和u的lca的点权大于等于d的节点。考虑到这是一棵最大生成树,每个点的父亲节点的点权不会大于这个节点。这也就意味着,我们需要找到u的最高的祖先,使得这个祖先的点权大于等于d。不妨称这个祖先为w,那么w的子树的所有叶子节点,就是u在d的降水下能抵达的节点。
于是,我们求出了第一个步骤的解。
然后我们考虑第二个步骤的解。考虑到这是一张无向图,我们先求出1号节点到所有节点的距离,然后把这些值赋到叶子节点上,不妨称它为『距离权值』。因为我们每一次求min必然是求「某个点的子树中所有叶子节点的『距离权值』的最小值」,那么就可以进行树形dp,把这个最小值的信息直接记录到每个虚拟节点上。
这就做完了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

const int N=800005,M=800005;
const int INF=0x3f3f3f3f;

inline int Min(int A,int B){
	return A<B?A:B;
}

struct ee{
	int v;
	int w;
	int a;
	int nxt;
}e[M<<1];
int h[N],et=0;
inline void Eadd(int U,int V,int W,int A){
	e[++et]=(ee){V,W,A,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W,int A){
	Eadd(U,V,W,A);
	Eadd(V,U,W,A);
}
struct tee{
	int v;
	int nxt;
}te[N<<1];
int g[N],tet=0;
inline void tEadd(int U,int V){
	te[++et]=(tee){V,g[U]};
	g[U]=et;
}
inline void tadd(int U,int V){
	tEadd(U,V);
	tEadd(V,U);
}
struct data{
	int u;int v;int a;
}lst[M];
inline bool cmp(const data &A,const data &B){
	return A.a>B.a;
}
int ff[N],f[N][20];
inline int fa(int X){
	return ff[X]==X?ff[X]:ff[X]=fa(ff[X]);
}
int val[N];
int n,m,cnt,rt;
inline void uni(int X,int Y){
	X=fa(X),Y=fa(Y);
	tadd(ff[X],cnt);tadd(ff[Y],cnt);
	ff[X]=ff[Y]=cnt;
}
inline void kruskal(){
	cnt=n;
	for(int i=1;i<=m;++i){
		if(fa(lst[i].u)==fa(lst[i].v)){
			continue;
		}
		val[++cnt]=lst[i].a;
		uni(lst[i].u,lst[i].v);
		if(cnt==n*2-1){
			break;
		}
	}
	rt=fa(1);
}
int dis[N],vis[N];
struct cmp2{
	inline bool operator()(int A,int B){
		return dis[A]>dis[B];
	}
};
priority_queue< int,vector<int>,cmp2 > q;
inline void dij(){
	for(int i=2;i<=n*2;++i){
		dis[i]=INF;vis[i]=0;
	}
	vis[1]=1,dis[1]=0;
	q.push(1);
	int p;
	while(!q.empty()){
		p=q.top();q.pop();vis[p]=0; 
		for(int i=h[p];i;i=e[i].nxt){
			if(dis[e[i].v]>dis[p]+e[i].w){
				dis[e[i].v]=dis[p]+e[i].w;
				if(!vis[e[i].v]){
					q.push(e[i].v);
				}
			}
		}
	}
}
inline void dfs0(int X){
	for(int i=g[X];i;i=te[i].nxt){
		if(te[i].v==f[X][0]){
			continue;
		}
//		printf("%d %d\n",X,te[i].v);
		f[te[i].v][0]=X;
		for(int j=1;j<=18;++j){
			f[te[i].v][j]=f[f[te[i].v][j-1]][j-1];
		}
		dfs0(te[i].v);
		dis[X]=Min(dis[X],dis[te[i].v]);
	}
}
inline int qry(int X,int D){
	for(int i=18;i>=0;--i){
		if(val[f[X][i]]>D){
			X=f[X][i];
		}
	}
	return dis[X];
}
void init(){
	scanf("%d%d",&n,&m);
	et=tet=0;
	for(int i=1;i<=n*2;++i){
		g[i]=h[i]=0;
	}
	int u,v,w,a;
	for(int i=1;i<=m;++i){
		scanf("%d%d%d%d",&u,&v,&w,&a);
		add(u,v,w,a);
		lst[i]=(data){u,v,a};
	}
	std::sort(lst+1,lst+1+m,cmp);
	for(int i=1;i<=n*2;++i){
		ff[i]=i;val[i]=INF;
	}
	kruskal();
	dij();
	dfs0(rt);
//	for(int i=1;i<=rt;++i){
//		printf("%d ",dis[i]);
//	}
//	puts("");
	int Q,K,S,lans=0,x,d;
	scanf("%d%d%d",&Q,&K,&S);
	for(int i=1;i<=Q;++i){
		scanf("%d%d",&x,&d);
		x=(x+lans*K-1)%n+1;d=(d+lans*K)%(S+1);
		printf("%d\n",lans=qry(x,d));
	}
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		init();
	}
	return 0;
}

lp1967 NOIP2013 货车运输

一道最大生成树加LCA的裸题。
因为是求路上权值最小的边权值最大,所以可以在最大生成树上跑。当然二分答案加01BFS也是一种想法,不过时间复杂度不对。
那么在最大生成树上很显然最大的路径上边权值最小。
所以在最大生成树上跑LCA,记录沿途路径最大值即可。
当然跑树剖也是可以的,不过很难写。

#include<iostream>
#include<cstdio>
#include<algorithm>

const int INF = 0x3f3f3f3f;

int n,m,q;

int FA[10005];
inline int fa( int X ){
    return X==FA[X]?X:(FA[X]=fa(FA[X]));
}
inline void mrg( int X, int Y ){
    X = fa( X ), Y = fa( Y );
    FA[X] = Y;
}

struct ee0{
    int u;
    int v;
    int w;
    inline bool operator < (const ee0 &B)const{
        return w > B.w;
    }
}e0[50005];

struct ee{
    int v;
    int w;
    int nxt;
}e[20005];
int h[10005],et=0;
inline void Add(int U,int V,int W){
    e[++et] = (ee){V,W,h[U]};
    h[U] = et;
}

int fi[10005][20],fv[10005][20],dep[10005];
bool vis[10005];
inline void dfs(int X,int FTHR){
    for(int i=h[X];i;i=e[i].nxt){
        if(vis[e[i].v]){
            continue;
        }
        vis[e[i].v]=1;
        fi[e[i].v][0]=X;
        fv[e[i].v][0]=std::min(fv[e[i].v][0],e[i].w);
        dep[e[i].v]=dep[X]+1;
        dfs(e[i].v,X);
    }
}

inline int lca(int X,int Y){
    dep[X]<dep[Y]?(X^=Y^=X^=Y):0;
    int ans=INF,dlt;
    if(X==Y){
        return 0;
    }
    for(dlt=15;dlt>=0;--dlt){
        if(dep[X]-(1<<dlt)>=dep[Y]){
            ans=std::min(ans,fv[X][dlt]);
            X=fi[X][dlt];
        }
    } 
    if(X==Y){
        return ans;
    }
    for(dlt=15;dlt>=0;--dlt){
        if(fi[X][dlt]!=fi[Y][dlt]){
            ans=std::min(ans,fv[X][dlt]);
            ans=std::min(ans,fv[Y][dlt]);
            X=fi[X][dlt],Y=fi[Y][dlt];
        }
    }
    ans=std::min(ans,fv[X][0]);
    ans=std::min(ans,fv[Y][0]);
    return ans;
}

void init(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&e0[i].u,&e0[i].v,&e0[i].w);
    }
    for(int i=1;i<=n;++i){
        FA[i]=i;
        fv[i][0]=INF;
    }
    std::sort(e0+1,e0+1+m);
    for(int i=1;i<=m;++i){
        if(fa(e0[i].v)!=fa(e0[i].u)){
            Add(e0[i].u,e0[i].v,e0[i].w);
            Add(e0[i].v,e0[i].u,e0[i].w);
            mrg(e0[i].u,e0[i].v);
        }
    }
    for(int i=1;i<=n;++i){
        if(FA[i]==i){
            fi[i][0]=0;
            fv[i][0]=0;
            vis[i]=1;
            dfs(i,0);
        }
    }
    scanf("%d",&q);
    for(int j=1;j<=15;++j){
        for(int i=1;i<=n;++i){
            fi[i][j]=fi[fi[i][j-1]][j-1];
            fv[i][j]=std::min(fv[i][j-1],fv[fi[i][j-1]][j-1]);
        }
    }
    int u,v;
    for(int i=1;i<=q;++i){
        scanf("%d%d",&u,&v);
        if(fa(u)!=fa(v)){
            puts("-1");
            continue;
        }
        printf("%d\n",lca(u,v));
    }
}

int main(){
    init();
    return 0;
}