首页 > 代码库 > [LCA]二月的最后一天来搞事情吧
[LCA]二月的最后一天来搞事情吧
先发模版题
codevs 2370 小机房的树
poj 1986 Distance Queries
poj 1330 Nearest Common Ancestors
感谢机房大佬xqmmcqs的代码
Tarjan版 http://www.cnblogs.com/xqmmcqs/p/5952293.html
树上倍增版 http://www.cnblogs.com/xqmmcqs/p/5954097.html
#include<cstdio> #define MAXN #define MAXQ int n,Q,heade[MAXN],headq[MAXN],fa[MAXN],lca[MAXQ],dis[MAXN],cnt; bool vis[MAXN]; struct edge { int v,next,val; }e[MAXN*2]; struct query { int u,v,next; }q[MAXQ*2]; void adde(int x,int y,int z) { e[++cnt].v=y; e[cnt].next=heade[x]; heade[x]=cnt; e[cnt].val=z; } void addq(int x,int y) { q[++cnt].u=x; q[cnt].v=y; q[cnt].next=headq[x]; headq[x]=cnt; } int getfa(int x)//并查集路径压缩 { return fa[x]=x==fa[x]?x:getfa(fa[x]); } int getdis(int i)//计算路径长度 { return dis[q[i<<1].u]+dis[q[i<<1].v]-2*dis[lca[i]]; } void Tarjan(int u) { fa[u]=u; vis[u]=true; for(int i=heade[u];i;i=e[i].next) { int v=e[i].v; if(!vis[v]) { dis[v]=dis[u]+e[i].val; Tarjan(v); fa[v]=u; } } for(int i=headq[u];i;i=q[i].next)//处理询问 { int v=q[i].u==u?q[i].v:q[i].u; if(vis[v])lca[i>>1]=getfa(fa[v]); } } int main() { scanf("%d",&n); int x,y,z; for(int i=1;i<n;i++) { scanf("%d%d%d",&x,&y,&z); adde(x,y,z); adde(y,x,z); } cnt=1; scanf("%d",&Q); for(int i=1;i<=Q;i++) { scanf("%d%d",&x,&y); addq(x,y); addq(y,x); } Tarjan(1); for(int i=1;i<=Q;i++) { printf("%d\n",getdis(i)); } return 0; }
#include<cstdio> #include<algorithm> using namespace std; struct edge { int v,next,val; }e[100005]; int n,m,heads[50005],fa[17][50005],dis[50005],dep[50005],cnt; void add(int u,int v,int val) { e[++cnt].next=heads[u]; heads[u]=cnt; e[cnt].v=v; e[cnt].val=val; } void dfs(int u)//预处理dep和fa[0][j] { for(int i=heads[u];i;i=e[i].next) { if(e[i].v!=fa[0][u]) { dep[e[i].v]=dep[u]+1; fa[0][e[i].v]=u; dis[e[i].v]=dis[u]+e[i].val; dfs(e[i].v); } } } int LCA(int u,int v) { if(dep[u]>dep[v])swap(u,v); for(int i=16;~i;i--) if(dep[fa[i][v]]>=dep[u]) v=fa[i][v]; if(u==v)return u; for(int i=16;~i;i--) if(fa[i][u]!=fa[i][v]) { u=fa[i][u]; v=fa[i][v]; } return fa[0][u]; } int main() { scanf("%d",&n); for(int i=1;i<n;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); } dep[1]=fa[0][1]=1; dfs(1); for(int i=1;i<=16;i++) for(int j=1;j<=n;j++) fa[i][j]=fa[i-1][fa[i-1][j]]; scanf("%d",&m); while(m--) { int x,y; scanf("%d%d",&x,&y); printf("%d\n",dis[x]+dis[y]-2*dis[LCA(x,y)]);//两点之间路径长度 } return 0; }
#include <bits/stdc++.h> using namespace std; #define Maxn 50005 #define Maxq 75005 int cnt=0,lan[Maxn],laq[Maxq],fa[Maxn],vis[Maxn],dis[Maxn],lca[Maxq]; struct edge { int u,v,n,c; }e[Maxn<<1]; struct que { int u,v,n; }q[Maxq<<1]; void adde(int u,int v,int c) { e[++cnt]=(edge){u,v,lan[u],c},lan[u]=cnt; e[++cnt]=(edge){v,u,lan[v],c},lan[v]=cnt; } void addq(int x,int y) { q[++cnt]=(que) {x,y,laq[x]},laq[x]=cnt; q[++cnt]=(que) {y,x,laq[y]},laq[y]=cnt; } int getfa(int x) { return fa[x]=x==fa[x]?x:getfa(fa[x]); } void tarjan(int u) { fa[u]=u; vis[u]=1; for (int i=lan[u];i;i=e[i].n) { int v=e[i].v; if (vis[v]==0) { dis[v]=dis[u]+e[i].c; tarjan(v); fa[v]=u; } } for (int i=laq[u];i;i=q[i].n) { int v=q[i].v; if (vis[v]) lca[i>>1]=getfa(fa[v]); } } int getdis (int i) { return dis[q[i<<1].u]+dis[q[i<<1].v]-(dis[lca[i]]<<1); } int main() { int n,m; scanf ("%d",&n); for (int i=1;i<n;i++) { int u,v,c; scanf ("%d %d %d",&u,&v,&c); adde(u,v,c); } scanf ("%d",&m); cnt=1; for (int i=1;i<=m;i++) { int x,y; scanf ("%d %d",&x,&y); addq(x,y); } tarjan (1); for (int i=1;i<=m;i++) { printf ("%d\n",getdis(i)); } }
一些玄学的事情
xqmmcqs Tarjan版本中第52行
int v=q[i].u==u?q[i].v:q[i].u;
可以直接替换成
int v=q[i].v;
以及
在codevs测2370小机房的树时,多开5个,大数据莫名其妙WA掉,多开10个就好了
以上
一七年二月的最后一天还有三个小时就结束了
准备搞点事情了
立一个flag好了
在一七年三月的第一天搞并查集,嗯,可能吧
最后一行献给可爱的男孩子们
[LCA]二月的最后一天来搞事情吧
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。