POJ PKU 1986 Distance Queries 解题报告

题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=1986

这是一道并查集+树的题,采用Tarjan离线算法

首先BS一下出题的人,也太懒了吧,还要我们看1984题才知道输入

题目的意思是告诉一个节点数为40000的树,问我们两个节点间的距离。实际上就是找出公共父节点,Tarjan算法写挫了很容易TLE,我开始用Vector就写搓了,结果TLE,后来重写,自己写邻接表然后AC了。

所谓离线算法就是把问题先全部读入,在处理树的对应节点的时候解决对应节点的问题

这里有个简单的优化,就是Tarjan算法要求对DNF(元素访问的顺序编号)做并查集,并且并入到父节点(就是编号小的那个节点),而这里可以对并查集做个小处理,使它一定是子节点并入父节点,这样可以省去DNF的计算(我的第一次TLE就没做这个优化),直接用节点的编号

关于Tarjan算法:http://www.nocow.cn/index.php/Tarjan%E7%AE%97%E6%B3%95

这道题里LCA函数可以加入记录当前节点到根节点的距离,再记录所有节点到根节点的距离,这样可以通过计算获得两节点的距离,省去不断访问父节点知道访问到公共父节点,避免浪费时间

PS:那个输入的方向C完全没用,仅仅是为了和1984题保持输入格式一致

代码如下:(C++)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

struct node
{
    node(){first = -1;}
    long dis;
    long first;
};

struct road
{
    long next, to, dis;
};

//并查集个人模板
long DSet[50005];
void init(long n)
{
    for( long i = 0 ; i <= n ; i ++)
        DSet[i] = i;
}
long findP( long id)
{
    if(DSet[id] != id)
        DSet[id] = findP(DSet[id]);
    return DSet[id];
}
//联合元素,这里修改为把b的父节点设为a,但是要在下面使用的时候注意不能搞反顺序
long UnionEle( long a, long b)
{
    a = findP(a);
    b = findP(b);
    DSet[b] = a;
    return a;
}

void lca(long pos, long dis);

bool ischeck[50005] = {false};
long res[20005] = {0};
long que[50005];
node point[50005];
road rd[50005 * 2];
road question[50005 * 2];

void insertR(long from, long to, long len, long &n)
{
    rd[n].to = to;
    rd[n].dis = len;
    rd[n].next = point[from].first;
    point[from].first = n;
    n ++;
}
void insertQ(long from, long to, long index, long &n)
{
    question[n].to = to;
    question[n].dis = index;
    question[n].next = que[from];
    que[from] = n;
    n ++;
}
int main()
{
    long n, m, i, j, k, from, to, len, rdl = 0, quel = 0;
    char c;
    scanf("%ld %ld", &n, &m);

    //Input roads
    for(i = 0; i < m; i ++)
    {

        scanf("%ld %ld %ld %c", &from, &to, &len, &c);
        insertR(from, to, len, rdl);
        insertR(to, from, len, rdl);
    }

    memset(que, -1, sizeof(que));
    scanf("%ld", &k);
    //Input question
    for(i = 0; i < k; i ++)
    {
        scanf("%ld %ld", &from, &to);
        insertQ(from, to, i, quel);
        insertQ(to, from, i, quel);
    }

    init(n);
    ischeck[1] = true;
    lca(1, 0);
    for(i = 0; i < k; i ++)
        printf("%ld\n", res[i]);
    return 0;
}

void lca(long pos, long dis)
{
    point[pos].dis = dis;
    long i, p;
    ischeck[pos] = true;
    for(i = point[pos].first; i != -1; i = rd[i].next)
    {
        if(ischeck[rd[i].to] == false)
        {
            lca(rd[i].to, dis + rd[i].dis);
            UnionEle(pos, rd[i].to);
        }
    }

    for(i = que[pos]; i != -1; i = question[i].next)
    {
        if(ischeck[question[i].to])
        {
            p = findP(question[i].to);
            res[question[i].dis] = dis + point[question[i].to].dis  - 2 * point[p].dis;
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏用户2442861的专栏

阿里巴巴2014秋季校园招聘-软件研发工程师笔试题详解

http://blog.csdn.net/zs634134578/article/details/21018845

1402
来自专栏数据结构与算法

HDU4352 XHXJ's LIS(LIS 状压)

刚开始的思路是$f[i][j]$表示到第$i$位,LIS长度为$j$的方案。 然而发现根本不能转移,除非知道了之前的状态然后重新dp一遍。。

933
来自专栏计算机视觉与深度学习基础

Leetcode 130 Surrounded Regions

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions su...

1965
来自专栏LhWorld哥陪你聊算法

【推荐系统篇】--推荐系统之训练模型

经过之前的训练数据的构建可以得到所有特征值为1的模型文件,本文将继续构建训练数据特征并构建模型。

1661
来自专栏我的技术专栏

数据结构图文解析之:哈夫曼树与哈夫曼编码详解及C++模板实现

1603
来自专栏java 成神之路

java.util.Random 实现原理

3355
来自专栏人工智能LeadAI

TensorFlow应用实战 | TensorFlow基础知识

hw = tf.constant("Hello World! Mtianyan love TensorFlow!")

1644
来自专栏JavaQ

HashMap扩容拾遗

JDK8中HashMap扩容涉及到的加载因子和链表转红黑树的知识点经常被作为面试问答题,本篇将对这两个知识点进行小结。

1112
来自专栏ACM算法日常

确定比赛名次(拓扑排序) - HDU 1285

这次先讲理论,因为拓扑排序在日常工作中用的并不多,甚至于很多人可能忘了计算机中存在这样一种排序。我大概的整理一下拓扑排序的定义和应用,以便看了这...

922
来自专栏漫漫深度学习路

tensorflow学习笔记(三十三):ExponentialMovingAverage

ExponentialMovingAverage Some training algorithms, such as GradientDescent and M...

4956

扫码关注云+社区

领取腾讯云代金券