lalalala


私信TA

用户名:zhangshuo

访问量:151546

签 名:

像狗一样的学习,像绅士一样地玩耍。

等  级
排  名 5
经  验 30084
参赛次数 10
文章发表 201
年  龄 12
在职情况 学生
学  校 芜湖市第十一中学
专  业

  自我简介:

今日懒惰流下的口水,将会成为明日里伤心的泪水。

刚做一道题:


1036 商务旅行


 时间限制: 1 s

 空间限制: 128000 KB

 题目等级 : 钻石 Diamond



题目描述 Description

某首都城市的商人要经常到各城镇去做生意,他们按自己的路线去做,目的是为了更好的节约时间。

假设有N个城镇,首都编号为1,商人从首都出发,其他各城镇之间都有道路连接,任意两个城镇之间如果有直连道路,在他们之间行驶需要花费单位时间。该国公路网络发达,从首都出发能到达任意一个城镇,并且公路网络不会存在环。

你的任务是帮助该商人计算一下他的最短旅行时间。

输入描述 Input Description

输入文件中的第一行有一个整数N,1<=n<=30 000,为城镇的数目。下面N-1行,每行由两个整数a 和b (1<=a, b<=n; a<>b)组成,表示城镇a和城镇b有公路连接。在第N+1行为一个整数M,下面的M行,每行有该商人需要顺次经过的各城镇编号。

输出描述 Output Description

    在输出文件中输出该商人旅行的最短时间。

样例输入 Sample Input

5
  1 2
  1 5
  3 5
   4 5 

                                                                       4

                                                                       1

                                                                       3
                                                                       2
                                                                       5

样例输出 Sample Output

7

数据范围及提示 Data Size & Hint

分类标签 Tags 点此展开 

最近公共祖先 图论 并查集 线段树 树结构



树链剖分求LCA:

定义:LCA(Lowest Common Ancestor 最近公共祖先)定义如下:在一棵树中两个节点的LCA为这两个节点所有的公共祖先中深度最大的节点。 


1111111111.jpg

代码:
这是一道典型的 LCA,可以使用倍增算法+stl,而stl主要体现在树的存储(std::vector)。
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int maxv=50010,max_log_v=25;
vector<int> G[maxv];// 图的邻接表表示
int parent[maxv][max_log_v],depth[maxv];
// 加边
void add_edge(int from,int to){
	G[from].push_back(to);
	G[to].push_back(from);
} 
void dfs(int root, int v) {// dfs 遍历树并预处理
    depth[v]=depth[root]+1;// 预处理出 parent[0] 和 depth, root 表示根节点的编号
    parent[v][0]=root;
    // 预处理出 parent
    for(int k=1;k<=20;k++)
        parent[v][k]=parent[parent[v][k-1]][k-1];
    for(int k=0;k<G[v].size();k++)
        if(G[v][k]!=root)
        	dfs(v,G[v][k]);
}
int lca(int u,int v) {// 计算u和v的LCA         	
	if(depth[u]>depth[v])swap(u, v);
	for(int k=0;k<=20;k++)
		if((depth[v]-depth[u])>>k&1)
			v=parent[v][k];
        // 利用二分搜索计算 LCA
	if(u==v)return u;
	for(int k=20;k>=0;k--)
		if (parent[u][k]!=parent[v][k]) {
			u=parent[u][k];
			v=parent[v][k];
		}
	return parent[u][0];
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<n;i++) {
		int from,to;
		cin>>from>>to;
		add_edge(from,to);
	}
	dfs(0,1);
	int m;
	cin>>m;
	int st[m+1];
	for(int i=1;i<=m;i++)
		cin>>st[i];
	int ans=0;
	for(int i=2;i<=m;i++)
		ans+=depth[st[i-1]]+depth[st[i]]-2*depth[lca(st[i-1],st[i])];
	cout<<ans<<endl;
	return 0;
}

 倍增 LCA + stl

 和大家分享一下爱这道蛮有趣的题目!


 

0.0分

0 人评分

  评论区

#include<bits/stdc++.h>
#define lli long long int
#define mid ((ll+rr)>>1)
#define debug cout
using namespace std;
const int maxn=3e4+1e2;
int s[2*maxn],t[2*maxn],nxt[2*maxn],fr[2*maxn],n,m,a,b;
int fa[maxn],top[maxn],son[maxn],siz[maxn],dep[maxn],num[maxn],seg[maxn];
bool vis[maxn];
int lson[8*maxn],rson[8*maxn],l[8*maxn],r[8*maxn],cnt;
lli dat[8*maxn],add[8*maxn],ans;

inline void addedge(int from,int to)
{
    static int cnt=0;
    t[++cnt]=to;
    nxt[cnt]=s[from];
    s[from]=cnt;
}

inline void dfs1(int pos)
{
    siz[pos]=1;
    int at=s[pos];
    while(at)
    {
        if(vis[t[at]])
2018-11-10 09:49:10
树剖LCA,比倍增快很多
2018-11-09 21:58:36
  • «
  • 1
  • »