网站的后缀,上海比较有名的景观设计公司,怎么做电影网站教程,福清建设局网站一、题目链接 P10289 [GESP样题 八级] 小杨的旅游 - 洛谷 二、题目大意 n个节点之间有n - 1条边#xff0c;其中k个节点是传送门#xff0c;任意两个传送门之间可以 以0单位地时间相互到达。问从u到v至少需要多少时间#xff1f; 三、解题思路 输入不必多讲。 cin … 一、题目链接 P10289 [GESP样题 八级] 小杨的旅游 - 洛谷 二、题目大意 n个节点之间有n - 1条边其中k个节点是传送门任意两个传送门之间可以 以0单位地时间相互到达。问从u到v至少需要多少时间 三、解题思路 输入不必多讲。 cin n k q;
for (int i 1; i n - 1; i) {int x, y;cin x y;e[x].push_back(y);e[y].push_back(x);
}
for (int i 1; i k; i) cin door[i]; BFSDFS 对于这个题目你肯定会想到用DFS和BFS直接去做。 但 或者 当然了更好的方法一定还有本文只是介绍了一种方法。 正解 分成两种方案使用传送门和不使用传送门取快者。 使用传送门 用BFS找到每个节点离最近传送点的距离存入dst数组结果就是从起点走到最近传送点 - 传送到离终点最近的传送点 - 走到终点 dst[u] dst[v] int dst[N]; // dst[i] i 到 离i最近的传送点 的距离void bfs() {memset(dst, 0x3f, sizeof (dst));queueint qu;for (int i 1; i k; i) {qu.push(door[i]); // 存入所有的传送点dst[door[i]] 0;}while (!qu.empty()) {int now qu.front();qu.pop();for (int x : e[now]) {if (dst[x] 0x3f3f3f3f) {dst[x] dst[now] 1; // 更新x离最近传送点的位置qu.push(x);}}}
}
...
{
...bfs();int res1 dst[u] dst[v];
...
}
... 不使用传送门 普通的BFS方法超时了这里介绍一种可行的方法(LCA) 什么是LCA LCA的意思是最近公共祖先如下图A与B的最近公共祖先是X。 如何用LCA计算A到B的距离 距离dist 首先计算每个节点离根的距离也就是深度 - 1。 A与B的距离 dist[A] dist[B] - 2 * dist[x] 建立dist int dist[N] {-1}; // dist[0] -1 dist[1]才能 0
void dfs(int fa, int x) {dist[x] dist[fa] 1;for (int u : e[x]) {if (u ! fa) // 不能走回头路 省去vis数组dfs(x, u);}
}
...
{
...dfs(0, 1); // 起初给一个无意义的0作为根节点的父亲
...
}
... 接着是lca函数 int lca(int u, int v); lca函数中有两个工作要做 1. 把u和v的深度化作一样 循环上移u或者v直到dist[u] dist[v] // 半伪代码
if (dist[u] dist[v])swap(u, v); // 保证v更深 要不停更新v
while (dist[u] dist[v]) {v v的父亲;
}
if (u v) // 如果在没有更新 u 的情况下两者相等 那已经找到了最近公共祖先return u; 2. u和v一起更新 直到两者相等就返回 // 半伪代码
while (u ! v) {u u的父亲;v v的父亲;
}
return u; 太慢了 u 或者 v一层一层上去可没时间。 极端情况下就是这样 每次处理数据都需要进行一次假设q 数据最大值循环次数就是(2 * 100000) ^ 2 40,000,000,000。 使用倍增法优化 我们把uv的第x个祖先看成2 ^ x 2 ^ y 2 ^ z... int f[N][20]; // f[x][i] 节点 x 的 第2^i 个祖先(从下往上) DFS中记录下任意节点的第2 ^ i个祖先如下包含原本的代码。 void dfs(int fa, int x) {dist[x] dist[fa] 1;f[x][0] fa; // x的第2^0(1)个祖先就是它爹for (int i 1; i 18; i)f[x][i] f[f[x][i - 1]][i - 1]; // x的第2^i个祖先就是 它2^(i-1)个祖先的第2^(i-1)个祖先 因为2^i 2^(i-1) 2^(i-1)for (int u : e[x]) {if (u ! fa)dfs(x, u);}
} LCA中也要改动。 int lca(int u, int v) {// 1if (dist[u] dist[v])swap(u, v);for (int i 18; i 0; i--) { // 2^18 2*10^5if (dist[u] dist[f[v][i]])v f[v][i];if (u v) return u;}//2for (int i 18; i 0; i--) {if (f[u][i] ! f[v][i])u f[u][i], v f[v][i];}return f[u][0]; // u和v最后是它们公共祖先的两个儿子 所以它们公共祖先是它们任意一个的父亲
} 块1i从18开始试探v的第2^i个祖先 是否 存在 并 深度大于等于u如果满足以上条件就把v变成v的第2^i个祖先然后i 1716...继续试探直到u v或i 0。 块2i同样从18开始试探v的第2^i个祖先 是否和 u的第2^i个祖先不相等如果不相等就更新u和v同上循环结束后u和v一定是它们最近公共祖先的两个儿子最后返回它们任意一个的父亲。 四、完整代码 长度有点小小的震撼但相信你已经看懂了。 #include iostream
#include cstring
#include queue
using namespace std;const int N 200005;vectorint e[N];
int n, k, q, door[N]; // door[] 存放每个传送点
int dist[N] {-1}, f[N][20]; // dist[] 每个点离根节点的距离 f[x][i] 节点 x 的 第2^i 个祖先(从下往上)
int dst[N]; // dst[i] i 到 离i最近的传送点 的距离void bfs() {memset(dst, 0x3f, sizeof (dst));queueint qu;for (int i 1; i k; i) {qu.push(door[i]); // 存入所有的传送点dst[door[i]] 0;}while (!qu.empty()) {int now qu.front();qu.pop();for (int x : e[now]) {if (dst[x] 0x3f3f3f3f) {dst[x] dst[now] 1; // 更新x离最近传送点的位置qu.push(x);}}}
}void dfs(int fa, int x) {dist[x] dist[fa] 1;f[x][0] fa;for (int i 1; i 18; i)f[x][i] f[f[x][i - 1]][i - 1];for (int u : e[x]) {if (u ! fa)dfs(x, u);}
}int lca(int u, int v) {if (dist[u] dist[v])swap(u, v);for (int i 18; i 0; i--) {if (dist[u] dist[f[v][i]])v f[v][i];if (u v) return u;}for (int i 18; i 0; i--) {if (f[u][i] ! f[v][i])u f[u][i], v f[v][i];}return f[u][0];
}int solve(int u, int v) {// ** 使用传送门int res1 dst[u] dst[v]; // 找离起点最近的传送点 传送至 离终点最近的传送点// **不使用传送门int res2 dist[u] dist[v] - 2 * dist[lca(u, v)];return min(res1, res2); // 取小者
}int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin n k q;for (int i 1; i n - 1; i) {int x, y;cin x y;e[x].push_back(y);e[y].push_back(x);}for (int i 1; i k; i) cin door[i];bfs();dfs(0, 1);while (q--) {int u, v;cin u v;cout solve(u, v) endl;}return 0;
}
