zoj一题求教
2838 - Utopia
时间限制:Java: 5000 ms / Others: 5000 ms
内存限制:Java: 32768 KB / Others: 32768 KB
问题描述
Few people know a secret nation in the world named Utopia. But I have been there before, where there are many beautiful villages. Seeing from the space, you will find that all the villages are connected together via some roads such that there is one and only one path between every two villages.
One day, when I was taking photos of this country, I met a handsome young man named Pierre who looked very worried. So I came up and wondered if I could do something for him. He told me that he had fallen in love with Mary, the most beautiful girl in his village A.
Every morning, Mary went to work in a bakery shop in the village B and she came home at 6 p.m in the evening. After a long time, Pierre couldn't wait telling Mary that he loved her, so he decided to wait for Mary and tell her his love in the village C.
Unfortunately, Pierre was not sure if C was on the path between B and his own village. He felt very upset.
Pierre's love moved me, but you know, I was a stranger there myself, and I knew little about Utopia. Therefore, I stayed with Pierre and waited for the help of some Wiseman.
Can you help him?
输入说明
There are multiple test cases for this problem.
Each test case starts with a line containing an integer N (1 <= N <= 50000), representing that there are totally N villages (indexed from 0 to N-1), followed by N - 1 lines which provide the road information in Utopia. Each line with the form 'V1 V2' (without quotation, 0 <= V1, V2 <= N-1) means that there is a bidirectional road between village V1 and V2. Then it's an integer M (1 <= M <= 500000), followed by M queries, each query is in the form of 'A B C' (without quotation, 0 <= A, B, C <= N-1) in a single line.
输出说明
For each test case, output "Case #:" first. "#" is the number of the case, which starts from 1. Then for each query 'A B C', if village C is on the path between village A and B, output 'Yes' (without quotation) in a single line, otherwise output 'No' (without quotation).
Separate two consecutive test cases with a blank line, but Do NOT output an extra blank line after the last one.
输入样例
3
0 1
1 2
3
0 2 1
1 2 0
1 2 1
输出样例
Case 1:
Yes
No
Yes
小提示
This problem has huge input and output data, please use 'scanf()' and 'printf()' instead of 'cin' and 'cout' to avoid timeout.
我是按着这个做的
1、如果点C当且仅当是其中一个节点的祖先时，那么C肯定在路径上
2、如果C是AB两点的共同祖先即CA（Common Ancestor），只要判断C是否为最低公共祖先（LCA）即可。
3、否则不在路径上
对于问题1，只要dfs一遍记录每个节点的入栈时间intime及出栈时间outtime，然后判断其
包含关系即可
对于问题2，注意到某个节点的所有儿子节点从左到右的intime和outtime是递增的，因此可以二分查找这个CA是否有更低的CA，如果有，说明其不是LCA
然后我的代码超时了 求教
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
#define MAX 50000
typedef struct node
{
int data;
struct node *next;
}Node;
typedef struct
{
int v, e;
Node **ver;
}Graph;
int in[MAX];
int out[MAX];
int visit[MAX];
int cnti = 1, cnto = 1;
int M, N;
int flag = 0;
int cnt = 1;
void Init(Graph *G)
{
int s, e;
int i;
Node *temp;
G->v = N;
G->e = G->v - 1;
G->ver = (Node **)malloc(sizeof(Node *) * G->v);
for (i = 0; i < G->v; i++)
{
G->ver[i] = (Node *)malloc(sizeof(Node));
G->ver[i]->next = NULL;
}
for (i = 0; i < G->e; i++)
{
scanf("%d%d", &s, &e);
temp = (Node *)malloc(sizeof(Node));
temp->data = s;
temp->next = G->ver[e]->next;
G->ver[e]->next = temp;
temp = (Node *)malloc(sizeof(Node));
temp->data = e;
temp->next = G->ver[s]->next;
G->ver[s]->next = temp;
}
}
void DFS(Graph G, int start)
{
Node *temp;
int v;
visit[start] = 1;
in[start] = cnti++;
temp = G.ver[start]->next;
while (temp)
{
v = temp->data;
if (!visit[v])
DFS(G, v);
temp = temp->next;
}
out[start] = cnto++;
}
int Judge(int child, int ancer)
{
if (in[ancer] < in[child] && out[ancer] > out[child])
return 1;
return 0;
}
void Check(Graph G)
{
int a, b, c;
int i, max, min;
int ans;
if (flag)
printf("\n");
flag = 1;
printf("Case %d:\n", cnt++);
while (M--)
{
scanf("%d%d%d", &a, &b, &c);
ans = 0;
if (a == c || b == c)
ans = 1;
else if ((Judge(a, c) && !Judge(b, c)) || (!Judge(a, c) && Judge(b, c)))
ans = 1;
else if (Judge(a, c) && Judge(b, c))
{
min = (in[a] > in[b] ? b : a);
max = (out[a] > out[b] ? a : b);
ans = 1;
for (i = 0; i < G.v; i++)
{
if (in[i] > in[c] && in[i] < in[min])
if (out[i] < out[c] && out[i] > out[max])
{
ans = 0;
break;
}
}
}
if (ans == 1)
printf("Yes\n");
else
printf("No\n");
}
}
int main()
{
Graph G;
while (1)
{
scanf("%d", &N);
if (!N)
break;
Init(&G);
scanf("%d", &M);
DFS(G, 0);
Check(G);
}
return 0;
}
