滁州网站开发,免费域名注册查询,海南网纹瓜,网站建设费用用还是一道比较明显的求LCA(最近公共祖先)模型的题目,我们可以使用多种方法来解决该问题#xff0c;这里我们使用更好写的离线的tarjan算法来解决该问题。 除去tarjan算法必用的基础数组#xff0c;我们还有一个数组d[],d[i]记录的是每个点的出度#xff0c;也就是它的延迟时间… 还是一道比较明显的求LCA(最近公共祖先)模型的题目,我们可以使用多种方法来解决该问题这里我们使用更好写的离线的tarjan算法来解决该问题。 除去tarjan算法必用的基础数组我们还有一个数组d[],d[i]记录的是每个点的出度也就是它的延迟时间以及数组w[],w[i]的含义是点i到根节点的延迟时间。在通过dfs求出每个点i的w[i]以后在tarjan中我们该如何求出两点的延迟时间呢
我们设点i到j的延迟时间为f(x),当我们求得i与j的最近公共祖先为anc我们首先让f(x)w[i]w[j] 但很明显我们多加了两w[anc]所以我们需要减去两倍的w[anc] 但延迟时间还包括经过anc的时间所以还得加上一个d[anc]。此处请结合w[]和d[]的含义理解。 最后能得出式子:f(x)w[i]w[h]−w[anc]2d[anc] 我们利用这个式子在tarjan函数中就能得出每个询问的答案当然对于起始和结束都在同一个节点的情况下,它的答案就是当前节点的出度我们可以进行特判一下。输入输出较多建议使用scanf和printf进行输入输出。
时间复杂度:dfs每个点遍历一次,复杂度级别O(n),tarjan算法复杂度接近 O(nm)。
#includebits/stdc.h
using namespace std;
typedef long long LL;
typedef pairint,int PII;
const int N100010;unordered_mapint,vectorint gra;
int n,m;
//单个点的出度
int d[N];
//记录点i到根节点的延迟
int w[N];
//并查集数组
int q[N];
//记录答案
int res[N];
int st[N];
//存下查询
vectorPII 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(gfa) 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 yitem.first,iditem.second;if(st[y]2){int ancfind(y);res[id]w[y]w[u]-w[anc]*2d[anc];}}st[u]2;
}
int main()
{cinnm;for(int i0;in-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 i0;im;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 i1;in;i) q[i]i;tarjan(1);for(int i0;im;i) printf(%d\n,res[i]);return 0;
}
错误答案:用floyd直接爆炸
错误答案
#includebits/stdc.h
using namespace std;
const int N1005,M1005;
int deg[N];//度
int dis[N][N];
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);memset(dis,0x7f,sizeof(dis));int n,m;cinnm;int v1,v2;for(int i1;in;i){cinv1v2;deg[v1];deg[v2]; }for(int i1;in;i){dis[v1][v2]deg[v1];dis[v2][v1]deg[v2];} for(int k1;kn;k)for(int v11;v1n;v1)for(int v21;v2n;v2)//枚举点if((v1!k)(v2!k)(v1!v2))dis[v1][v2]min(dis[v1][v2],dis[v1][k]dis[k][v2]);int start,end; while(m--){cinstartend;coutdis[start][end]deg[end];}return 0;
}
/*
4 3
1 2
1 3
2 4
2 3
3 4
3 3
*/
