刚做一道题:
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为这两个节点所有的公共祖先中深度最大的节点。
代码: 这是一道典型的 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]])
树剖LCA,比倍增快很多
Biggest Number (C++代码)回溯法浏览:1599 |
C语言程序设计教程(第三版)课后习题9.8 (Java代码)浏览:1622 |
蛇行矩阵 (C语言代码)浏览:742 |
WU-printf基础练习2 (C++代码)浏览:1996 |
WU-拆分位数 (C++代码)浏览:775 |
模拟计算器 (C++代码)浏览:798 |
陶陶摘苹果2 (C语言代码)浏览:595 |
C语言训练-排序问题<1> (C语言代码)浏览:355 |
10月月赛题解浏览:536 |
C语言训练-斐波纳契数列 (C语言代码)浏览:593 |