浙江龙网

  1. 首页 > 生活百科 > >

Pictionary 方法记录( 二 )

生活百科


审题题意转化：
有\(n\)座城市；有\(m\)个时刻，在第\(i\)个时刻，所有\(m-i+1\)的倍数之间连边；有\(q\)个询问，询问第\(x_i\)座城市和第\(y_i\)座城市什么时候连通 。
连边（合并）连通城市的过程，其实就是对多个点建立集合，并进行合并的过程，所以考虑使用并查集 。
在对两个城市进行连边（即合并两个点）时，钦定第一个城市是第二个城市的父亲节点，并记录这两个点合并时的时间戳 。
查询现询问两个点\((x,y)\)的最早连通时间 。\((x,y)\)的最早连通时间就是\(x\)到\(lca(x,y)\)中的最大时间戳加上\(lca(x,y)\)到\(y\)中的最大时间戳 。
为什么是最大值？两个城市要想连通，就必须要等到路径上最后一条边建好才行 。
为什么是\(lca\)？题目中城市\(x\)和城市\(y\)的连通抽象到图上就是\(x\)到\(y\)的一条树上路径（同一条边不能重复走），也就是\(x\)->\(lca(x,y)\)->\(y\).这里不能包含\(lca(x,y)\)，因为这个点储存的时间戳是和另一个点击合并的时间 。
考虑\(lca\)的求法 。在处理并查集的时候，其实就处理出的图上的每一个父子关系，我们可以将其利用起来：根据这些父子关系，\(x\)和\(y\)往上跳，从而找到\(lca(x,y)\).
但要想保存父子关系就不能使用路径压缩 ， 所以采用启发式合并：将小集合合并到大集合，以起到优化的作用 。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=100010;int n,m,q;int f[N],siz[N],dfn[N],dep[N];struct Edge//链式前向星存图{ int u,v,nex;}e[N<<1];int head[N],tot;void add(int u,int v){ tot++; e[tot].u=u; e[tot].v=v; e[tot].nex=head[u]; head[u]=tot;}int maxx(int a,int b){ return a>b?a:b;}int find(int x)//并查集查找（不能用路径压缩）{ if(x==f[x]) return x; return find(f[x]);}void dfs(int u)//dfs求每个点相对于超级祖先的深度{ for(int i=head[u];i;i=e[i].nex) {int v=e[i].v;dep[v]=dep[u]+1;dfs(v); }}int main(){ scanf("%d%d%d",&n,&m,&q); int rt; for(int i=1;i<=n;i++) {f[i]=i;siz[i]=0; } for(int i=m;i>=1;i--) {for(int j=(i<<1);j<=n;j+=i)//对所有m-i+1的倍数之间连边{int dx=find(i),dy=find(j);if(dx==dy){continue;}if(siz[dx]<siz[dy])//启发式合并，将小集合合并到大集合{swap(dx,dy);}f[dy]=dx;add(dx,dy);rt=dx;//rt最终会记录所有点的公共祖先，钦定这个“超级祖先”为根节点if(siz[dx]==siz[dy]){siz[dx]++;}dfn[dy]=m-i+1;//dfn记录合并时的时间戳} } dfs(rt); for(int i=1;i<=q;i++) {int x,y;scanf("%d%d",&x,&y);int ans=0;if(dep[x]<dep[y]){swap(x,y);}while(dep[x]>dep[y]){ans=maxx(ans,dfn[x]);x=f[x];}while(x!=y){ans=maxx(maxx(dfn[x],dfn[y]),ans);x=f[x],y=f[y];}printf("%d\n",ans); }}参考

推荐阅读


上一篇：FlinkSql之TableAPI详解

下一篇：有用的内置Node.js APIs