|
|
以前没见过“最近公共祖先”这一类的题啊。长见识了，呵呵。
解法基本上就是
http://www.cppblog.com/varg-vikernes/archive/2010/03/10/109355.html
这篇文章里面提到的两种方法。
两种方法的解法都非常精妙！
最后程序写出来：
Tarjan 3372K 219MS
DFS+RMQ 7992K 329MS
代码
Tarjan：
 #include <stdio.h>
#define MAX_N 40032
#define MAX_Q 10032
  struct edge_node  {
 struct edge_node *next;
int idx, len;
 };
struct edge_node edges[MAX_N*2];
struct tree_node {
struct edge_node *edge;
struct query_node *query;
int depth, visited;
};
struct tree_node tree[MAX_N];
struct query_node {
int idx, ans;
struct query_node *next;
};
struct query_node queries[MAX_Q*2];
struct set_node {
int parent, len;
};
struct set_node set[MAX_N];
__inline int max(int a, int b)
{
return a > b ? a : b;
}
__inline int find(int idx)
{
static int stack[MAX_N];
int i, sp;
  for (sp = 0; set[idx].parent; sp++) {
stack[sp] = idx;
idx = set[idx].parent;
 }
for (sp--; sp >= 0; sp--) {
i = stack[sp];
set[i].len += set[set[i].parent].len;
set[i].parent = idx;
}
return idx;
}
__inline void add_edge(int idx, int a, int b, int len)
{
struct edge_node *p = &edges[idx];
p->idx = b;
p->len = len;
p->next = tree[a].edge;
tree[a].edge = p;
}
__inline void add_query(int idx, int a, int b)
{
struct query_node *p = &queries[idx];
p->idx = b;
p->next = tree[a].query;
tree[a].query = p;
}
void dfs(int idx, int depth)
{
struct edge_node *e;
struct query_node *q;
int i;
tree[idx].visited = 1;
tree[idx].depth = depth;
for (q = tree[idx].query; q; q = q->next) {
if (!tree[q->idx].visited)
continue;
i = find(q->idx);
q->ans = tree[q->idx].depth + depth - 2*tree[i].depth;
}
for (e = tree[idx].edge; e; e = e->next) {
if (tree[e->idx].visited)
continue;
dfs(e->idx, depth + e->len);
set[e->idx].parent = idx;
set[e->idx].len = e->len;
}
}
int main()
{
int n, m, k, i, a, b, len;
char str[16];
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &n, &m);
for (i = 0; i < m*2; i += 2) {
scanf("%d%d%d%s", &a, &b, &len, str);
add_edge(i, a, b, len);
add_edge(i+1, b, a, len);
}
scanf("%d", &k);
for (i = 0; i < k*2; i += 2) {
scanf("%d%d", &a, &b);
add_query(i, a, b);
add_query(i+1, b, a);
}
dfs(1, 0);
for (i = 0; i < k*2; i += 2)
printf("%d\n", max(queries[i].ans, queries[i+1].ans));
return 0;
}
DFS+RMQ：
#include <stdio.h>
#define MAX_N 40032
int rmq[MAX_N*2][16], seq[MAX_N*2], seq_cnt, map[MAX_N];
struct edge_node {
struct edge_node *next;
int idx, len;
};
struct edge_node edges[MAX_N*2];
struct tree_node {
struct edge_node *edge;
int depth, visited;
};
struct tree_node tree[MAX_N];
__inline int min(int a, int b)
{
return a < b ? a : b;
}
__inline void add_edge(int idx, int a, int b, int len)
{
struct edge_node *p = &edges[idx];
p->idx = b;
p->len = len;
p->next = tree[a].edge;
tree[a].edge = p;
}
__inline void add_seq(int idx)
{
seq[seq_cnt] = idx;
if (!map[idx])
map[idx] = seq_cnt;
seq_cnt++;
}
void dfs(int idx, int depth)
{
struct edge_node *e;
tree[idx].visited = 1;
tree[idx].depth = depth;
for (e = tree[idx].edge; e; e = e->next) {
if (tree[e->idx].visited)
continue;
add_seq(idx);
add_seq(e->idx);
dfs(e->idx, depth + e->len);
}
}
__inline void rmq_init()
{
int i, len, j;
for (i = 1; i < seq_cnt; i++)
rmq[i][0] = tree[seq[i]].depth;
for (i = 1; ; i++) {
len = 1 << i;
if (1 + len > seq_cnt)
break;
for (j = 1; j + len <= seq_cnt; j++)
rmq[j][i] = min(rmq[j][i - 1], rmq[j + len/2][i - 1]);
}
}
__inline int rmq_query(int start, int end)
{
int len, i;
len = end - start + 1;
for (i = 0; (1 << i) <= len; i++);
i--;
return min(rmq[start][i], rmq[end + 1 - (1 << i)][i]);
}
int main()
{
int n, m, i, j, a, b, len;
char str[16];
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &n, &m);
for (i = 0; i < m*2; i += 2) {
scanf("%d%d%d%s", &a, &b, &len, str);
add_edge(i, a, b, len);
add_edge(i+1, b, a, len);
}
seq_cnt = 1;
dfs(1, 0);
rmq_init();
scanf("%d", &i);
while (i--) {
scanf("%d%d", &a, &b);
if (map[a] > map[b]) {
j = a;
a = b;
b = j;
}
j = rmq_query(map[a], map[b]);
printf("%d\n", tree[a].depth + tree[b].depth - 2*j);
}
return 0;
}
|