目录
- 1.机房
- 1.问题描述
- 2.输入格式
- 3.输出格式
- 4.样例输入
- 5.样例说明
- 6.数据范围
- 7.原题链接
- 2.解题思路
- 3.Ac_code
- tarjan
- 倍增LCA
1.机房
1.问题描述
这天, 小明在机房学习。
他发现机房里一共有 台电脑, 编号为 1 到 , 电脑和电脑之间有网线连 接, 一共有 根网线将
小明发现每台电脑转发、发送或者接受信息需要的时间取决于这台电脑和 多少台电脑直接相连, 而信息在网线中的传播时间可以忽略。比如如果某台电脑 用网线直接连接了另外 台电脑, 那么任何经过这台电脑的信息都会延迟
小明一共产生了 个疑问: 如果电脑 向电脑 发送信息, 那么信息从 传到
2.输入格式
输入共 行, 第一行为两个正整数
后面 行, 每行两个正整数 表示编号为 和
后面 行, 每行两个正整数 表示小明的第
3.输出格式
输出共 行, 第 行一个正整数表示小明第
4.样例输入
4 3
1 2
1 3
2 4
2 3
3 4
3 3
5.样例说明
这四台电脑各自的延迟分别为 2,2,1,1。
对于第一个询问, 从 2 到 3 需要经过 2,1,3, 所以时间和为 2+2+1=5 。
对于第二个询问, 从 3 到 4 需要经过 3,1,2,4, 所以时间和为 1+2+2+1=6。
对于第三个询问, 从 3 到 3 只会产生一次延迟, 所以时间为 1 。
6.数据范围
7.原题链接
机房
2.解题思路
还是一道比较明显的求
LCA
(最近公共祖先)模型的题目,我们可以使用多种方法来解决该问题，这里我们使用更好写的离线的
tarjan
算法来解决该问题 (已补充倍增做法)。
除去
tarjan
算法必用的基础数组，我们还有一个数组
d[]
,
d[i]
记录的是每个点的出度，也就是它的延迟时间，以及数组
w[]
,
w[i]
的含义是点
i
到根节点的延迟时间。在通过
dfs
求出每个点
i
的
w[i]
以后，在
tarjan
中我们该如何求出两点的延迟时间呢？
我们设点
i
到
j
的延迟时间为,当我们求得
i
与
j
的最近公共祖先为
anc
，我们首先让,但很明显，我们多加了两遍，所以我们需要减去两倍的，但延迟时间还包括经过
anc
的时间，所以还得加上一个。此处请结合
w[]
和
d[]
的含义理解。
最后能得出式子:
假设图中当求到D
的延迟时间，根据数组定义我们可知 为四点的延迟时间之和。为三点延迟之和。从E
到D
点所求应该是四点之和。E
和D
的最近公共祖先为E
,可以看出对于从B
点开始一直到根节点这一段我们是不需要的，也就是被多加了两遍，所以我们应该减去。但最后答案点本身是应该计算进来的，所以我们单独加进来。其中即为，可得式子:B
3.Ac_code
tarjan
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N=100010;
unordered_map<int,vector<int>> gra;
int n,m;
//单个点的出度
int d[N];
//记录点i到根节点的延迟
int w[N];
//并查集数组
int q[N];
//记录答案
int res[N];
int st[N];
//存下查询
vector<PII> query[N];
//并查集查询
int find(int x){
if(x!=q[x]) q[x]=find(q[x]);
return q[x];
}
void dfs(int u,int fa)
{
w[u]+=d[u];
for(auto g:gra[u]){
if(g==fa) continue;
w[g]+=w[u];
dfs(g,u);
}
}
void tarjan(int u)
{
st[u]=1;
for(auto j:gra[u]){
if(!st[j])
{
tarjan(j);
q[j]=u;
}
}
for(auto item: query[u]){
int y=item.first,id=item.second;
if(st[y]==2){
int anc=find(y);
res[id]=w[y]+w[u]-w[anc]*2+d[anc];
}
}
st[u]=2;
}
int main()
{
cin>>n>>m;
for(int i=0;i<n-1;++i){
int a,b;
scanf("%d%d",&a,&b);
gra[a].push_back(b);
gra[b].push_back(a);
d[a]++,d[b]++;
}
for(int i=0;i<m;++i){
int a,b;
scanf("%d%d",&a,&b);
if(a!=b){
query[a].push_back({b,i});
query[b].push_back({a,i});
}else{
res[i]=d[a];
}
}
dfs(1,-1);
for(int i=1;i<=n;++i) q[i]=i;
tarjan(1);
for(int i=0;i<m;++i) printf("%d\n",res[i]);
return 0;
} 倍增LCA
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
const int N = 200010;
std::vector<int> e[N];
int n, m;
int depth[N], fa[N][30];
int root;
int w[N], d[N];
void bfs(int root)
{
memset(depth, 0x3f, sizeof depth);
depth[0] = 0, depth[root] = 1;
queue<int> q;
q.push(root);
while (!q.empty()) {
auto t = q.front();
q.pop();
for (auto j : e[t]) {
if (depth[j] > depth[t] + 1) {
depth[j] = depth[t] + 1;
q.push(j);
fa[j][0] = t;
for (int k = 1; k <= 15; k++) {
fa[j][k] = fa[fa[j][k - 1]][k - 1];
}
}
}
}
}
int lca(int a, int b) {
if (depth[a] < depth[b]) swap(a, b);
for (int k = 20; k >= 0; k--) {
if (depth[fa[a][k]] >= depth[b]) {
a = fa[a][k];
}
}
if (a == b) return a;
for (int k = 20; k >= 0; --k) {
if (fa[a][k] != fa[b][k]) {
a = fa[a][k];
b = fa[b][k];
}
}
return fa[a][0];
}
void dfs(int u, int fa)
{
w[u] += d[u];
for (auto g : e[u]) {
if (g == fa) continue;
w[g] += w[u];
dfs(g, u);
}
}
void solve()
{
cin >> n >> m;
for (int i = 0; i < n - 1; ++i) {
int a, b;
cin >> a >> b;
e[a].push_back(b);
e[b].push_back(a);
d[a]++, d[b]++;
}
dfs(1, -1);
bfs(1);
for (int i = 0; i < m; ++i)
{
int a, b;
cin >> a >> b;
int c = lca(a, b);
cout << w[a] + w[b] - w[c] * 2 + d[c] << '\n';
}
}
int main()
{
solve();
return 0;
} ![swmm与lisflood-fp源码如何一起编译 CMake命令[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)