博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
poj 1470 Closest Common Ancestors (LCA)
阅读量:5822 次
发布时间:2019-06-18

本文共 3193 字,大约阅读时间需要 10 分钟。

Closest Common Ancestors
Time Limit: 2000MS   Memory Limit: 10000K
Total Submissions: 14314   Accepted: 4607

Description

Write a program that takes as input a rooted tree and a list of pairs of vertices. For each pair (u,v) the program determines the closest common ancestor of u and v in the tree. The closest common ancestor of two nodes u and v is the node w that is an ancestor of both u and v and has the greatest depth in the tree. A node can be its own ancestor (for example in Figure 1 the ancestors of node 2 are 2 and 5)

Input

The data set, which is read from a the std input, starts with the tree description, in the form: 
nr_of_vertices 
vertex:(nr_of_successors) successor1 successor2 ... successorn 
...
where vertices are represented as integers from 1 to n ( n <= 900 ). The tree description is followed by a list of pairs of vertices, in the form: 
nr_of_pairs 
(u v) (x y) ... 
The input file contents several data sets (at least one). 
Note that white-spaces (tabs, spaces and line breaks) can be used freely in the input.

Output

For each common ancestor the program prints the ancestor and the number of pair for which it is an ancestor. The results are printed on the standard output on separate lines, in to the ascending order of the vertices, in the format: ancestor:times 
For example, for the following tree: 

Sample Input

55:(3) 1 4 21:(0)4:(0)2:(1) 33:(0)6(1 5) (1 4) (4 2)      (2 3)(1 3) (4 3)

Sample Output

2:15:5

Hint

Huge input, scanf is recommended.

Source

 

模板题:

给出在线做法和离线做法:

在线的DFS+RMQ做法:

1 //444K    485MS    C++    2082B    2014-04-15 19:41:38 2 #include
3 #include
4 #include
5 #define N 1005 6 struct node{ 7 int u,v; 8 int next; 9 }edge[2*N];10 int n,num,to,head[N];11 int set[2*N],dep[2*N];12 int rank[N],vis[N];13 int dp[2*N][30];14 void addedge(int u,int v)15 {16 edge[num].u=u;17 edge[num].v=v;18 edge[num].next=head[u];19 head[u]=num++;20 }21 int Min(int a,int b)22 {23 return dep[a]
y) return set[RMQ(y,x)];59 else return set[RMQ(x,y)];60 }61 int main(void)62 {63 int m,u,v,mm;64 int in[N];65 while(scanf("%d",&n)!=EOF)66 {67 memset(in,0,sizeof(in));68 memset(vis,0,sizeof(vis));69 memset(head,-1,sizeof(head));70 num=0;71 for(int i=0;i
View Code

 

离线的Tarjan做法:

1 //3024K    563MS    C++    1575B    2014-04-15 20:32:44 2 //Runtime Error 了好几次 T T  3 #include
4 #include
5 #include
6 #define N 1005 7 using namespace std; 8 vector
child[N],V[N]; 9 int set[N],vis[N];10 int in[N];11 int n;12 void init()13 {14 for(int i=0;i<=n;i++){15 child[i].clear();16 V[i].clear();17 }18 memset(vis,0,sizeof(vis));19 memset(in,0,sizeof(in));20 }21 int find(int x)22 {23 if(set[x]!=x) set[x]=find(set[x]);24 return set[x];25 }26 void merge(int a,int b)27 {28 int x=find(a);29 int y=find(b);30 set[y]=x;31 }32 void LCA(int u)33 {34 set[u]=u;35 vis[u]=true;36 for(int i=0;i
View Code

 

转载于:https://www.cnblogs.com/GO-NO-1/p/3667256.html

你可能感兴趣的文章
初探Angular6.x---进入用户编辑模块
查看>>
计算机基础知识复习
查看>>
【前端词典】实现 Canvas 下雪背景引发的性能思考
查看>>
大佬是怎么思考设计MySQL优化方案的?
查看>>
<三体> 给岁月以文明, 给时光以生命
查看>>
Android开发 - 掌握ConstraintLayout(九)分组(Group)
查看>>
springboot+logback日志异步数据库
查看>>
Typescript教程之函数
查看>>
Android 高效安全加载图片
查看>>
vue中数组变动不被监测问题
查看>>
3.31
查看>>
类对象定义 二
查看>>
收费视频网站Netflix:用户到底想要“点”什么?
查看>>
MacOS High Sierra 12 13系统转dmg格式
查看>>
关于再次查看已做的多选题状态逻辑问题
查看>>
动态下拉菜单,非hover
查看>>
政府安全资讯精选 2017年第十六期 工信部发布关于规范互联网信息服务使用域名的通知;俄罗斯拟建立备用DNS;Google打击安卓应用在未经同意情况下收集个人信...
查看>>
简单易懂的谈谈 javascript 中的继承
查看>>
iOS汇编基础(四)指针和macho文件
查看>>
Laravel 技巧锦集
查看>>