hdu-2586 How far away ?(lca+bfs+dfs+线段树)
2024-08-30 23:25:20
题目链接:
How far away ?
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
Problem Description
There are n houses in the village and some bidirectional roads connecting them. Every day peole always like to ask like this "How far is it if I want to go from house A to house B"? Usually it hard to answer. But luckily int this village the answer is always unique, since the roads are built in the way that there is a unique simple path("simple" means you can't visit a place twice) between every two houses. Yout task is to answer all these curious people.
Input
First line is a single integer T(T<=10), indicating the number of test cases.
For each test case,in the first line there are two numbers n(2<=n<=40000) and m (1<=m<=200),the number of houses and the number of queries. The following n-1 lines each consisting three numbers i,j,k, separated bu a single space, meaning that there is a road connecting house i and house j,with length k(0<k<=40000).The houses are labeled from 1 to n.
Next m lines each has distinct integers i and j, you areato answer the distance between house i and house j.
For each test case,in the first line there are two numbers n(2<=n<=40000) and m (1<=m<=200),the number of houses and the number of queries. The following n-1 lines each consisting three numbers i,j,k, separated bu a single space, meaning that there is a road connecting house i and house j,with length k(0<k<=40000).The houses are labeled from 1 to n.
Next m lines each has distinct integers i and j, you areato answer the distance between house i and house j.
Output
For each test case,output m lines. Each line represents the answer of the query. Output a bland line after each test case.
Sample Input
2
3 2
1 2 10
3 1 15
1 2
2 3
2 2
1 2 100
1 2
2 1
Sample Output
10
25
100
100
题意:
给一个无向图,问两点i和j之间的距离是多少;
思路:
由于询问规模大,所以就无向图转化成树,然后寻找lca,然后再算距离;
把lca转化成RMQ问题,我是用的线段树找的RMQ;
AC代码:
#include <bits/stdc++.h>
using namespace std;
const int N=4e4+;
typedef long long ll;
const double PI=acos(-1.0);
int n,m,t,dis[N],dep[N],vis[N],w[N];
vector<int>ve[N];
queue<int>qu;
int u[N],v[N],d[N],fa[N],a[*N],tot,first[N];
struct Tree
{
int l,r,ans;
};
Tree tree[*N];
void bfs()//bfs把图转化成树;
{
qu.push();
vis[]=;
dep[]=;
while(!qu.empty())
{
int top=qu.front();
qu.pop();
int len=ve[top].size();
for(int i=;i<len;i++)
{
int x=ve[top][i];
if(!vis[x])
{
vis[x]=;
qu.push(x);
dep[x]=dep[top]+;
fa[x]=top;
}
}
}
}
int dfs(int num)//dfs找到lca的数组,并计算i到1的dis
{
vis[num]=;
first[num]=tot;
a[tot++]=num;
int len=ve[num].size();
for(int i=;i<len;i++)
{
int x=ve[num][i];
if(vis[x])
{
dis[x]=dis[num]+d[x];
dfs(x);
a[tot++]=num;
}
}
}
void Pushup(int node)
{
if(dep[a[tree[*node].ans]]>=dep[a[tree[*node+].ans]])tree[node].ans=tree[*node+].ans;
else tree[node].ans=tree[*node].ans;
}//tree[node].ans为数组里的lca的位置;
void build(int node,int L,int R)
{
tree[node].l=L;
tree[node].r=R;
if(L>=R)
{
tree[node].ans=L;
return ;
}
int mid=(L+R)>>;
build(*node,L,mid);
build(*node+,mid+,R);
Pushup(node);
}
int query(int node,int L,int R)
{
if(L<=tree[node].l&&R>=tree[node].r)return tree[node].ans;
int mid=(tree[node].l+tree[node].r)>>;
if(R<=mid)return query(*node,L,R);
else if(L>mid)return query(*node+,L,R);
else
{
int pos1=query(*node,L,mid),pos2=query(*node+,mid+,R);
if(dep[a[pos1]]>=dep[a[pos2]])return pos2;
else return pos1;
}
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
ve[i].clear();
}
for(int i=;i<n;i++)
{
scanf("%d%d%d",&u[i],&v[i],&w[i]);
ve[u[i]].push_back(v[i]);
ve[v[i]].push_back(u[i]);
}
memset(vis,,sizeof(vis));
bfs();
for(int i=;i<n;i++)
{
if(fa[u[i]]==v[i])
{
d[u[i]]=w[i];
}
else
{
d[v[i]]=w[i];
}
}
tot=;
dfs();
build(,,tot-);
int ql,qr;
for(int i=;i<m;i++)
{
scanf("%d%d",&ql,&qr);
int pos;
if(first[ql]<=first[qr])
pos=query(,first[ql],first[qr]);
else pos=query(,first[qr],first[ql]);
printf("%d\n",dis[ql]-dis[a[pos]]-dis[a[pos]]+dis[qr]);
}
}
return ;
}
最新文章
- [C#6] 6-表达式形式的成员函数
- Java迷宫游戏
- Predicate接口和Consumer接口
- maven项目部署打包
- 信号量互斥,王明学learn
- TYVJ 1074 武士风度的牛
- Android Material Design:NavigationView抽屉导航菜单
- ImageView 设置OnTouchListener
- html和css实现一级菜单和二级菜单学习笔记
- yum安装配置mongoDB客户端和服务器端
- Android 4.4 Kitkat 使能 USB adb 功能
- MVC生成CheckBoxList并对其验证
- 个人作业3——个人总结(Alpha阶段)
- 洛谷 P1091 合唱队形
- Unity 查找泛型List中的相同与不同数据
- api测试工具
- 第三个Sprint冲刺第八天(燃尽图)
- 【翻译】TCP backlog在Linux中的工作原理
- jquery 根据自定义属性选择
- NPF or NPCAP service is not installed
热门文章
- mysql MHA报错 Can&#39;t exec ";mysqlbinlog";: No such file or directory at /usr/local/share/perl5/MHA/BinlogManager.pm line 99.
- typedef 与 define 的区别
- asp.net母版-页脚制作
- 【Sprint3冲刺之前】软件开发计划书
- 关于C++项目指针对象未被初始化的问题(0xcdcdcd)
- 一份还热乎的蚂蚁面经(已拿Offer)!附答案!!
- MySQL联表更新插入数据
- Android应用的电量消耗和优化的策略
- C# WinForm退出方法
- 九度OJ 1078:二叉树遍历 (二叉树)