lca 最近公共祖先

http://poj.org/problem?id=1330

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #define mt(a,b) memset(a,b,sizeof(a))
  5 using namespace std;
  6 const int inf=0x3f3f3f3f;
  7 class LCA { ///最近公共祖先 build_o(n*logn) query_o(1)
  8     typedef int typec;///边权的类型
  9     static const int ME=2e4+10;///边的个数
 10     static const int MV=1e4+10;///点的个数
 11     static const int MR=MV<<1;///rmq的个数
 12     struct E {
 13         int v,next;
 14         typec w;
 15     } e[ME];
 16     int le,head[MV],H[MV],dex[MR],aa[MR],bb[MR],raa[MR][20],rbb[MR][20],Index;
 17     typec dist[MV];
 18     void init_dex() {
 19         dex[0]=-1;
 20         for(int i=1; i<MR; i++) {
 21             dex[i]=dex[i>>1]+1;
 22         }
 23     }
 24     void dfs(int u,int fa,int level) {
 25         aa[Index]=u;
 26         bb[Index++]=level;
 27         for(int i=head[u]; ~i; i=e[i].next) {
 28             int v=e[i].v;
 29             if(v==fa) continue;
 30             dist[v]=dist[u]+e[i].w;
 31             dfs(v,u,level+1);
 32             aa[Index]=u;
 33             bb[Index++]=level;
 34         }
 35     }
 36 public:
 37     LCA() { init_dex();};
 38     void init() {
 39         le=Index=0;
 40         mt(head,-1);
 41     }
 42     void add(int u,int v,typec w) {
 43         e[le].v=v;
 44         e[le].w=w;
 45         e[le].next=head[u];
 46         head[u]=le++;
 47     }
 48     void build(int root) {
 49         dist[root]=0;
 50         dfs(root,-1,0);
 51         mt(H,-1);
 52         mt(rbb,0x3f);
 53         for(int i=0; i<Index; i++) {
 54             int tmp=aa[i];
 55             if(H[tmp]==-1) H[tmp]=i;
 56             rbb[i][0]=bb[i];
 57             raa[i][0]=aa[i];
 58         }
 59         for(int i=1; (1<<i)<=Index; i++) {
 60             for(int j=0; j+(1<<i)<Index; j++) {
 61                 int next=j+(1<<(i-1));
 62                 if(rbb[j][i-1]<=rbb[next][i-1]) {
 63                     rbb[j][i]=rbb[j][i-1];
 64                     raa[j][i]=raa[j][i-1];
 65                 } else {
 66                     rbb[j][i]=rbb[next][i-1];
 67                     raa[j][i]=raa[next][i-1];
 68                 }
 69             }
 70         }
 71     }
 72     int query(int l,int r) {
 73         l=H[l];
 74         r=H[r];
 75         if(l>r) swap(l,r);
 76         int p=dex[r-l+1];
 77         r-=(1<<p)-1;
 78         return rbb[l][p]<=rbb[r][p]?raa[l][p]:raa[r][p];
 79     }
 80     typec getdist(int l,int r) {
 81         return dist[l]+dist[r]-2*dist[query(l,r)];
 82     }
 83 } gx;
 84 
 85 const int M=1e4+10;
 86 int du[M];
 87 int main() {
 88     int t,n,u,v;
 89     while(~scanf("%d",&t)) {
 90         while(t--) {
 91             scanf("%d",&n);
 92             gx.init();
 93             mt(du,0);
 94             for(int i=1; i<n; i++) {
 95                 scanf("%d%d",&u,&v);
 96                 du[v]++;
 97                 gx.add(u,v,1);
 98                 gx.add(v,u,1);
 99             }
100             int rt=1;
101             for(int i=1; i<=n; i++) {
102                 if(du[i]==0) {
103                     rt=i;
104                     break;
105                 }
106             }
107             gx.build(rt);
108             scanf("%d%d",&u,&v);
109             printf("%d
",gx.query(u,v));
110         }
111     }
112     return 0;
113 }
View Code

http://poj.org/problem?id=1470

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cctype>
  4 #include<algorithm>
  5 #define mt(a,b) memset(a,b,sizeof(a))
  6 using namespace std;
  7 int getint(){
  8     int res=0;
  9     char tmp;
 10     while(!isdigit(tmp=getchar()));
 11     do{
 12         res=(res<<3)+(res<<1)+tmp-'0';
 13     }while(isdigit(tmp=getchar()));
 14     return res;
 15 }
 16 
 17 class LCA { ///最近公共祖先 build_o(n*logn) query_o(1)
 18     typedef int typec;///边权的类型
 19     static const int ME=2e3+10;///边的个数
 20     static const int MV=1e3+10;///点的个数
 21     static const int MR=MV<<1;///rmq的个数
 22     struct E {
 23         int v,next;
 24         typec w;
 25     } e[ME];
 26     int le,head[MV],H[MV],dex[MR],aa[MR],bb[MR],raa[MR][20],rbb[MR][20],Index;
 27     typec dist[MV];
 28     void init_dex() {
 29         dex[0]=-1;
 30         for(int i=1; i<MR; i++) {
 31             dex[i]=dex[i>>1]+1;
 32         }
 33     }
 34     void dfs(int u,int fa,int level) {
 35         aa[Index]=u;
 36         bb[Index++]=level;
 37         for(int i=head[u]; ~i; i=e[i].next) {
 38             int v=e[i].v;
 39             if(v==fa) continue;
 40             dist[v]=dist[u]+e[i].w;
 41             dfs(v,u,level+1);
 42             aa[Index]=u;
 43             bb[Index++]=level;
 44         }
 45     }
 46 public:
 47     LCA() {
 48         init_dex();
 49     };
 50     void init() {
 51         le=Index=0;
 52         mt(head,-1);
 53     }
 54     void add(int u,int v,typec w) {
 55         e[le].v=v;
 56         e[le].w=w;
 57         e[le].next=head[u];
 58         head[u]=le++;
 59     }
 60     void build(int root) {///传入树根
 61         dist[root]=0;
 62         dfs(root,-1,0);
 63         mt(H,-1);
 64         mt(rbb,0x3f);
 65         for(int i=0; i<Index; i++) {
 66             int tmp=aa[i];
 67             if(H[tmp]==-1) H[tmp]=i;
 68             rbb[i][0]=bb[i];
 69             raa[i][0]=aa[i];
 70         }
 71         for(int i=1; (1<<i)<=Index; i++) {
 72             for(int j=0; j+(1<<i)<Index; j++) {
 73                 int next=j+(1<<(i-1));
 74                 if(rbb[j][i-1]<=rbb[next][i-1]) {
 75                     rbb[j][i]=rbb[j][i-1];
 76                     raa[j][i]=raa[j][i-1];
 77                 } else {
 78                     rbb[j][i]=rbb[next][i-1];
 79                     raa[j][i]=raa[next][i-1];
 80                 }
 81             }
 82         }
 83     }
 84     int query(int l,int r) {///查lca
 85         l=H[l];
 86         r=H[r];
 87         if(l>r) swap(l,r);
 88         int p=dex[r-l+1];
 89         r-=(1<<p)-1;
 90         return rbb[l][p]<=rbb[r][p]?raa[l][p]:raa[r][p];
 91     }
 92     typec getdist(int l,int r) {///查两点最短距离
 93         return dist[l]+dist[r]-2*dist[query(l,r)];
 94     }
 95 } g;
 96 
 97 int ans[1024];
 98 int du[1024];
 99 int main(){
100     int n,m,u,v;
101     while(~scanf("%d",&n)){
102         g.init();
103         mt(du,0);
104         for(int i=0;i<n;i++){
105             u=getint();
106             m=getint();
107             while(m--){
108                 v=getint();
109                 du[v]++;
110                 g.add(u,v,1);
111                 g.add(v,u,1);
112             }
113         }
114         int root=1;
115         for(int i=2;i<=n;i++){
116             if(du[i]==0){
117                 root=i;
118                 break;
119             }
120         }
121         g.build(root);
122             m=getint();
123             mt(ans,0);
124 //            printf("m=%d
",m);
125             for(int i=0;i<m;i++){
126                 u=getint();
127                 v=getint();
128 //                printf("u=%d v=%d
",u,v);
129                 ans[g.query(u,v)]++;
130 //                printf("m=%d
",m);
131             }
132 //            puts("out");
133             for(int i=1;i<=n;i++){
134                 if(ans[i]){
135                     printf("%d:%d
",i,ans[i]);
136                 }
137             }
138 
139     }
140     return 0;
141 }
View Code

http://poj.org/problem?id=1986

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #define mt(a,b) memset(a,b,sizeof(a))
  5 using namespace std;
  6 const int inf=0x3f3f3f3f;
  7 //const int M=100010;
  8 class LCA { ///最近公共祖先 build_o(n*logn) query_o(1)
  9     typedef int typec;///边权的类型
 10     static const int ME=2e5+10;///边的个数
 11     static const int MV=1e5+10;///点的个数
 12     static const int MR=MV<<1;///rmq的个数
 13     struct E {
 14         int v,next;
 15         typec w;
 16     } e[ME];
 17     int le,head[MV],H[MV],dex[MR],aa[MR],bb[MR],raa[MR][20],rbb[MR][20],Index;
 18     typec dist[MV];
 19     void init_dex() {
 20         dex[0]=-1;
 21         for(int i=1; i<MR; i++) {
 22             dex[i]=dex[i>>1]+1;
 23         }
 24     }
 25     void dfs(int u,int fa,int level) {
 26         aa[Index]=u;
 27         bb[Index++]=level;
 28         for(int i=head[u]; ~i; i=e[i].next) {
 29             int v=e[i].v;
 30             if(v==fa) continue;
 31             dist[v]=dist[u]+e[i].w;
 32             dfs(v,u,level+1);
 33             aa[Index]=u;
 34             bb[Index++]=level;
 35         }
 36     }
 37 public:
 38     LCA() {
 39         init_dex();
 40     };
 41     void init() {
 42         le=Index=0;
 43         mt(head,-1);
 44     }
 45     void add(int u,int v,typec w) {
 46         e[le].v=v;
 47         e[le].w=w;
 48         e[le].next=head[u];
 49         head[u]=le++;
 50     }
 51     void build(int root) {///传入树根
 52         dist[root]=0;
 53         dfs(root,-1,0);
 54         mt(H,-1);
 55         mt(rbb,0x3f);
 56         for(int i=0; i<Index; i++) {
 57             int tmp=aa[i];
 58             if(H[tmp]==-1) H[tmp]=i;
 59             rbb[i][0]=bb[i];
 60             raa[i][0]=aa[i];
 61         }
 62         for(int i=1; (1<<i)<=Index; i++) {
 63             for(int j=0; j+(1<<i)<Index; j++) {
 64                 int next=j+(1<<(i-1));
 65                 if(rbb[j][i-1]<=rbb[next][i-1]) {
 66                     rbb[j][i]=rbb[j][i-1];
 67                     raa[j][i]=raa[j][i-1];
 68                 } else {
 69                     rbb[j][i]=rbb[next][i-1];
 70                     raa[j][i]=raa[next][i-1];
 71                 }
 72             }
 73         }
 74     }
 75     int query(int l,int r) {///查lca
 76         l=H[l];
 77         r=H[r];
 78         if(l>r) swap(l,r);
 79         int p=dex[r-l+1];
 80         r-=(1<<p)-1;
 81         return rbb[l][p]<=rbb[r][p]?raa[l][p]:raa[r][p];
 82     }
 83     typec getdist(int l,int r) {///查两点最短距离
 84         return dist[l]+dist[r]-2*dist[query(l,r)];
 85     }
 86 } gx;
 87 
 88 #include<cctype>
 89 int getint(){
 90     int res=0;
 91     char tmp;
 92     while(!isdigit(tmp=getchar()));
 93     do{
 94         res=(res<<3)+(res<<1)+tmp-'0';
 95     }while(isdigit(tmp=getchar()));
 96     return res;
 97 }
 98 int main(){
 99     int n,m,x,y,z;
100     char op[4];
101     while(~scanf("%d%d",&n,&m)){
102         gx.init();
103         while(m--){
104 //            scanf("%d%d%d%s",&x,&y,&z,op);
105             x=getint();
106             y=getint();
107             z=getint();
108             gx.add(x,y,z);
109             gx.add(y,x,z);
110         }
111 //        scanf("%d",&m);
112         m=getint();
113         gx.build(1);
114         while(m--){
115 //            scanf("%d%d",&x,&y);
116             x=getint();
117             y=getint();
118             printf("%d
",gx.getdist(x,y));
119         }
120     }
121     return 0;
122 }
View Code

end

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/gaolzzxin/p/4504692.html